UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#205087#3646. 调分LJ071001145ms8812kbC++111.6kb2024-06-23 09:01:252024-06-23 13:02:19

answer

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define pb emplace_back
#define sz(a) int(a.size())

const int N = 1e5 + 5;
int n, m, s[N], l[N], r[N], x[N], y[N];
vector<int> disc, vec[N];
int d[N], lc[N];
priority_queue<int, vector<int>, greater<int>> Q;

inline int askd(int x) {
  return lower_bound(disc.begin(), disc.end(), x) - disc.begin();
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> s[i] >> l[i] >> r[i], ++r[i];
  }
  disc.pb(1e9 + 1), disc.pb(0);
  for (int i = 1; i <= m; ++i) {
    cin >> x[i] >> y[i];
    disc.pb(x[i] - 1);
  }
  sort(disc.begin(), disc.end());
  disc.erase(unique(disc.begin(), disc.end()), disc.end());
  fill_n(d, sz(disc), int(1e9));
  for (int i = 1; i <= m; ++i) {
    int pos = askd(x[i]);
    d[pos] = min(d[pos], y[i]);
  }
  for (int i = 1; i < sz(disc); ++i) {
    d[i] = min(d[i], d[i - 1]);
  }
  for (int i = 0; i < sz(disc); ++i) {
    d[i] = d[i] - d[i + 1];
  }
  for (int i = 1; i <= n; ++i) {
    vec[askd(r[i])].pb(l[i]);
  }
  int ans = 0;
  for (int i = sz(disc) - 1, sum = 0; ~i; --i) {
    sum += d[i];
    for (auto v : vec[i]) {
      if (sum) {
        ++ans, --sum, Q.emplace(v);
      }else if (sz(Q) && Q.top() < v) {
        int u = Q.top();
        Q.pop(), Q.emplace(v);
        if (u < 0) {
          continue; 
        }
        ++lc[askd(u)];
      }else {
        ++lc[askd(v)];
      }
    }
    while (sum && lc[i]) {
      Q.emplace(-1), --lc[i], --sum;
    }
    ans -= lc[i];
  }
  cout << ans << '\n';
  return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 2ms
memory: 3644kb

input:

15 20
845403345 390609697 980384063
186743724 104990508 963496192
263966340 55953443 787815158
16843...

output:

11

result:

ok single line: '11'

Test #2:

score: 5
Accepted
time: 2ms
memory: 3640kb

input:

15 20
710914207 97234432 738264088
42243279 26728414 621680880
162908406 61586483 185903807
39356031...

output:

8

result:

ok single line: '8'

Test #3:

score: 5
Accepted
time: 0ms
memory: 3640kb

input:

15 20
700412807 672433278 902231896
862757701 298427492 916841742
374302689 72499348 943626637
99857...

output:

11

result:

ok single line: '11'

Test #4:

score: 5
Accepted
time: 0ms
memory: 3640kb

input:

15 20
293265775 187997853 409823298
5464414 1343941 440699330
960988144 265922201 963233253
94420468...

output:

8

result:

ok single line: '8'

Test #5:

score: 5
Accepted
time: 0ms
memory: 3644kb

input:

15 20
461991159 231524604 559439691
5940502 5556321 345367655
903635605 249803497 922750941
22099036...

output:

13

result:

ok single line: '13'

Test #6:

score: 5
Accepted
time: 0ms
memory: 3652kb

input:

200 20
526801273 451267596 669703900
117452796 52230219 581138048
986865963 924965003 996753167
3894...

output:

180

result:

ok single line: '180'

Test #7:

score: 5
Accepted
time: 0ms
memory: 3652kb

input:

200 20
697923362 12116150 916555730
164808860 137308876 177851204
848793719 656245263 936591222
2852...

output:

180

result:

ok single line: '180'

Test #8:

score: 5
Accepted
time: 0ms
memory: 3652kb

input:

200 20
161787269 2568546 247988992
585198193 135846344 900057943
616735835 226367000 704675057
61717...

output:

171

result:

ok single line: '171'

Test #9:

score: 5
Accepted
time: 0ms
memory: 3660kb

input:

200 200
657239333 380683702 843825391
528714786 13173880 984499662
475669898 456612694 833254921
494...

output:

140

result:

ok single line: '140'

Test #10:

score: 5
Accepted
time: 4ms
memory: 3660kb

input:

200 200
909293380 560881903 968880531
971017373 170045342 974022370
65272918 29942253 432191198
6343...

output:

119

result:

ok single line: '119'

Test #11:

score: 5
Accepted
time: 0ms
memory: 3656kb

input:

200 200
939041723 556876806 957997424
697350341 455737278 746435146
445674199 362307255 658553145
14...

output:

174

result:

ok single line: '174'

Test #12:

score: 5
Accepted
time: 0ms
memory: 3660kb

input:

200 200
797241149 541897259 988623827
286876319 100634468 629979548
706691378 249253522 768355649
53...

output:

158

result:

ok single line: '158'

Test #13:

score: 5
Accepted
time: 121ms
memory: 8540kb

input:

100000 100000
113998910 1 427605660
605845930 1 705422321
151459006 1 883297089
387565910 1 76233795...

output:

80577

result:

ok single line: '80577'

Test #14:

score: 5
Accepted
time: 125ms
memory: 8808kb

input:

100000 100000
254892569 1 447083628
483853444 1 731264529
334949412 1 349769789
990131147 1 99641344...

output:

91658

result:

ok single line: '91658'

Test #15:

score: 5
Accepted
time: 136ms
memory: 8812kb

input:

100000 100000
681865203 340942769 927067423
862581764 707438427 956358388
116698514 8707590 75316147...

output:

91886

result:

ok single line: '91886'

Test #16:

score: 5
Accepted
time: 151ms
memory: 8504kb

input:

100000 100000
261331494 48983905 881868750
781830534 695641946 888787608
53260475 3830725 603231233
...

output:

61713

result:

ok single line: '61713'

Test #17:

score: 5
Accepted
time: 150ms
memory: 8812kb

input:

100000 100000
293506655 235651927 491497166
438822357 265156420 853923925
751934202 175188320 797954...

output:

87719

result:

ok single line: '87719'

Test #18:

score: 5
Accepted
time: 156ms
memory: 8812kb

input:

100000 100000
842554959 79038413 923174446
409500140 348943344 708184830
167573117 117904906 7803893...

output:

80630

result:

ok single line: '80630'

Test #19:

score: 5
Accepted
time: 152ms
memory: 8808kb

input:

100000 100000
228364413 22596352 445742699
624348298 29932170 795936020
608997744 551190379 83387823...

output:

92773

result:

ok single line: '92773'

Test #20:

score: 5
Accepted
time: 146ms
memory: 8812kb

input:

100000 100000
482819933 162045322 954408191
299330487 19663334 576950439
84528908 37965318 245372349...

output:

93410

result:

ok single line: '93410'

Extra Test:

score: 0
Extra Test Passed