ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#205087 | #3646. 调分 | LJ07 | 100 | 1145ms | 8812kb | C++11 | 1.6kb | 2024-06-23 09:01:25 | 2024-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;
}
Details
小提示:点击横条可展开更详细的信息
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