QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#453643 | #1132. Financial Report | makrav | 5 | 145ms | 18504kb | C++20 | 1.9kb | 2024-06-24 05:55:02 | 2024-06-24 05:55:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct segtree {
int n;
vector<int> t;
segtree() = default;
segtree(int n_) {
n = n_;
t.assign(4 * n, 0);
}
void upd(int v, int tl, int tr, int p, int vl) {
if (tl + 1 == tr) {
t[v] = vl;
return;
}
int tm = (tl + tr) / 2;
if (p < tm) upd(v * 2, tl, tm, p, vl);
else upd(v * 2 + 1, tm, tr, p, vl);
t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int get(int v, int tl, int tr, int l, int r) {
if (l <= tl && tr <= r) return t[v];
if (tr <= l || tl >= r) return 0;
int tm = (tl + tr) / 2;
return max(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm, tr, l, r));
}
};
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, d; cin >> n >> d;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector<int> ord(n);
for (int i = 0; i < n; i++) ord[i] = i;
sort(ord.begin(), ord.end(), [&](int i, int j) {
return a[i] < a[j];
});
vector<int> pos(n);
for (int i = 0; i < n; i++) pos[ord[i]] = i;
vector<int> prv(n, 0);
prv[ord[0]] = -1;
for (int i = 1; i < n; i++) {
if (a[ord[i]] == a[ord[i - 1]]) prv[ord[i]] = prv[ord[i - 1]];
else prv[ord[i]] = i - 1;
}
segtree sg_all(n), sg_low(n);
vector<int> dp(n, 0);
for (int i = 0; i < n; i++) {
int mx_all = sg_all.get(1, 0, n, 0, n), mx_low = 1;
if (prv[i] != -1) {
mx_low = sg_low.get(1, 0, n, 0, prv[i] + 1) + 1;
}
dp[i] = max(mx_low, mx_all);
sg_all.upd(1, 0, n, i, dp[i]);
sg_low.upd(1, 0, n, pos[i], mx_low);
if (i - d >= 0) {
sg_all.upd(1, 0, n, i - d, 0);
sg_low.upd(1, 0, n, pos[i - d], 0);
}
}
cout << dp[n - 1] << '\n';
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 14
Accepted
time: 0ms
memory: 3868kb
input:
1 1 314159265
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
1 1 0
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
1 1 1000000000
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
2 1 299792458 299792458
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
2 1 141421356 173205080
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
2 1 244948974 223606797
output:
1
result:
ok single line: '1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 2 299792458 299792458
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
2 2 141421356 173205080
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
2 2 244948974 223606797
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
3 1 500000000 1000000000 0
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
3 2 500000000 1000000000 0
output:
2
result:
ok single line: '2'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
4 1 0 1000000000 200000000 500000000
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
4 2 0 1000000000 200000000 500000000
output:
3
result:
ok single line: '3'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
5 2 111111111 888888888 555555555 222222222 444444444
output:
2
result:
ok single line: '2'
Test #15:
score: -14
Wrong Answer
time: 0ms
memory: 3632kb
input:
19 1 876813783 876813783 294665595 1000000000 515198511 876813783 876813783 294665595 403855901 439947219 439947219 403855901 581007064 294665595 1000000000 581007064 294665595 865289906 865289906
output:
3
result:
wrong answer 1st lines differ - expected: '5', found: '3'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #62:
score: 12
Accepted
time: 100ms
memory: 18412kb
input:
300000 1 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 285899902 2...
output:
1
result:
ok single line: '1'
Test #63:
score: -12
Wrong Answer
time: 131ms
memory: 18428kb
input:
299971 1 213313757 312061773 790195557 213313757 0 790195557 30936680 832403554 312061773 30936680 0 213313757 329317874 329317874 0 0 329317874 329317874 0 213313757 329317874 790195557 832403554 832403554 329317874 312061773 832403554 832403554 329317874 329317874 312061773 790195557 790195557 790...
output:
6
result:
wrong answer 1st lines differ - expected: '7', found: '6'
Subtask #5:
score: 5
Accepted
Test #76:
score: 5
Accepted
time: 66ms
memory: 18260kb
input:
300000 300000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...
output:
1
result:
ok single line: '1'
Test #77:
score: 0
Accepted
time: 111ms
memory: 18216kb
input:
299994 299994 799095588 515641284 851040998 371590609 581412250 114983578 870953189 65883574 114983578 546636247 675572999 416143410 763181943 799095588 564152084 521371792 455808474 799095588 870953189 839155298 684313832 605076527 675572999 219704773 684313832 372618560 875093839 41381734 11498357...
output:
85
result:
ok single line: '85'
Test #78:
score: 0
Accepted
time: 127ms
memory: 18392kb
input:
299967 299967 55436237 815265051 726638198 232614559 766667170 589412354 222916094 881505795 351969379 185039621 500722663 929961726 12106126 527589224 131615979 740414875 483735803 961030961 685115515 630631167 847411283 606876236 853479813 969869770 978153478 951567612 284079913 655441675 23301827...
output:
1000
result:
ok single line: '1000'
Test #79:
score: 0
Accepted
time: 145ms
memory: 18384kb
input:
300000 300000 501796523 297945585 927399536 440670566 495542465 80848196 28003478 540869900 992383926 48799286 967913195 572970230 215873915 538679144 853459893 70385046 947090071 440258092 348827388 912684078 519842448 805256446 548573509 148406683 373586707 74817790 975254107 599779344 939526125 4...
output:
1079
result:
ok single line: '1079'
Test #80:
score: 0
Accepted
time: 123ms
memory: 18424kb
input:
300000 300000 863887522 425397042 713124005 773467613 489882500 437277345 139704179 557800941 215336895 161026143 927354002 294297768 165771354 512842947 537130652 175822358 136551779 148723787 79361863 416871734 644501573 743434372 557135739 94545556 438248865 141290994 550236652 94773186 137640908...
output:
119010
result:
ok single line: '119010'
Test #81:
score: 0
Accepted
time: 142ms
memory: 18484kb
input:
300000 300000 261069220 62324615 942003105 79398536 881237922 660291668 342301327 287380444 258811488 67001231 625514902 572229121 938217290 244331276 295213680 418810760 250148739 681986353 93691086 258512344 334478574 842247076 289652772 232932429 900601662 770838744 512730335 879450985 799339736 ...
output:
4195
result:
ok single line: '4195'
Test #82:
score: 0
Accepted
time: 77ms
memory: 18392kb
input:
300000 300000 0 3000 6000 9000 12000 15000 18000 21000 24000 27000 30000 33000 36000 39000 42000 45000 48000 51000 54000 57000 60000 63000 66000 69000 72000 75000 78000 81000 84000 87000 90000 93000 96000 99000 102000 105000 108000 111000 114000 117000 120000 123000 126000 129000 132000 135000 13800...
output:
300000
result:
ok single line: '300000'
Test #83:
score: 0
Accepted
time: 75ms
memory: 18256kb
input:
300000 300000 1000000000 999997000 999994000 999991000 999988000 999985000 999982000 999979000 999976000 999973000 999970000 999967000 999964000 999961000 999958000 999955000 999952000 999949000 999946000 999943000 999940000 999937000 999934000 999931000 999928000 999925000 999922000 999919000 99991...
output:
1
result:
ok single line: '1'
Test #84:
score: 0
Accepted
time: 91ms
memory: 18384kb
input:
298001 298001 34832 79106 92233 41187 22866 85580 32085 65715 113345 78332 61133 129921 63730 69451 73358 152855 121615 76292 134438 105458 81917 6956 78765 162590 107750 159413 169971 115829 134528 131661 75589 115759 143187 97623 223499 186250 151499 168707 105513 236574 176390 103994 237829 22505...
output:
87419
result:
ok single line: '87419'
Test #85:
score: 0
Accepted
time: 114ms
memory: 18384kb
input:
299000 299000 21957810 19402999 14174232 1584658 23477964 9979277 9164532 22323998 21003307 7443362 11819189 14661748 5803988 13596735 14666310 13535681 6460845 4003025 22441699 11909961 17684693 22096644 3463574 10789456 23133078 971943 20299903 1829387 6699896 17730801 1731607 17750814 7072208 903...
output:
4790
result:
ok single line: '4790'
Test #86:
score: 0
Accepted
time: 119ms
memory: 18504kb
input:
300000 300000 18367526 39162436 46248746 53023958 58166604 60555798 128617672 154424917 171357763 178047421 179307707 186820325 216560886 238860292 244781586 284718360 288356348 337385547 341190169 345812663 352395427 353945030 361546670 367410573 386805472 420176531 495081945 500301991 502134964 51...
output:
1124
result:
ok single line: '1124'
Test #87:
score: 0
Accepted
time: 120ms
memory: 18312kb
input:
300000 300000 998504892 998265952 997934075 997214275 997098713 996128339 995808017 995445379 994380027 994042007 994039412 993364233 993318976 992223668 991102126 990845586 987858596 987274453 986989530 986543852 986441325 986249054 986094401 985671270 985225560 984404578 984003136 983470456 983176...
output:
225
result:
ok single line: '225'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%