QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #311859 | #7605. Yet Another Mex Problem | Cocoly1990 | TL | 1452ms | 257748kb | C++17 | 3.9kb | 2024-01-22 21:34:46 | 2024-01-22 21:34:47 |
Judging History
answer
// Stop the noise and stop the clocks
// Problem: J. Yet Another Mex Problem
// Contest: Codeforces - MEX Foundation Contest (supported by AIM Tech)
// URL: https://codeforces.com/gym/102412/problem/J
// Time: 2024-01-22 20:28:59
// Memory Limit: 512 MB
// Author: Cocoly1990
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2e5 + 7, SEG_SIZE = N * 80;
const i64 inf = 0x3f3f3f3f3f3f3f3f;
struct Line {
i64 k, b;
Line (i64 k = 0, i64 b = -inf) : k (k), b (b) {}
i64 val (i64 x) {
return 1ll * k * x + b;
}
} info[SEG_SIZE];
struct Node {
int cnt = 0, L[SEG_SIZE], R[SEG_SIZE];
void insert (int &p, i64 l, i64 r, Line g) {
if (! p) {
p = ++ cnt;
info[p] = g;
return void ();
}
i64 mid = (l + r) >> 1;
if (info[p].val (mid) < g.val (mid)) swap (info[p], g);
if (g.k > info[p].k) insert (R[p], mid + 1, r, g);
else insert (L[p], l, mid, g);
}
i64 query (int p, i64 l, i64 r, int x) {
if (! p or l == r) return info[p].val (x);
i64 res = info[p].val (x);
i64 mid = (l + r) >> 1;
if (x <= mid) res = max (res, query (L[p], l, mid, x));
else res = max (res, query (R[p], mid + 1, r, x));
return res;
}
} t;
struct Seg {
int rt[N << 2];
i64 V;
void modify (int p, int l, int r, int x, Line g) {
t.insert (rt[p], 0, V, g);
if (l == r) {
assert (l == x);
return void ();
}
int mid = (l + r) >> 1;
if (x <= mid) modify (p << 1, l, mid, x, g);
else modify (p << 1 | 1, mid + 1, r, x, g);
}
i64 query (int p, int l, int r, int ql, int qr, i64 x) {
if (ql <= l and r <= qr) return t.query (rt[p], 0, V, x);
int mid = (l + r) >> 1;
i64 res = -inf;
if (ql <= mid) res = max (res, query (p << 1, l, mid, ql, qr, x));
if (qr > mid) res = max (res, query (p << 1 | 1, mid + 1, r, ql, qr, x));
return res;
}
} seg1, seg2;
struct Segmex {
int mn[N << 2];
void modify (int p, int l, int r, int x, int k) {
if (l == r) {
assert (l == x);
mn[p] = k;
return void ();
}
int mid = (l + r) >> 1;
if (x <= mid) modify (p << 1, l, mid, x, k);
else modify (p << 1 | 1, mid + 1, r, x, k);
mn[p] = min (mn[p << 1], mn[p << 1 | 1]);
}
i64 query (int p, int l, int r, int ql, int qr) {
if (ql <= l and r <= qr) return mn[p];
i64 res = inf;
int mid = (l + r) >> 1;
if (ql <= mid) res = min (res, query (p << 1, l, mid, ql, qr));
if (qr > mid) res = min (res, query (p << 1 | 1, mid + 1, r, ql, qr));
return res;
}
int find (int p, int l, int r, int x) {
if (l == r) return l;
int mid = (l + r) >> 1;
if (mn[p << 1] <= x) return find (p << 1, l, mid, x);
else return find (p << 1 | 1, mid + 1, r, x);
}
} segmx;
int n, K, a[N];
i64 sum[N], f[N];
int main () {
cin >> n >> K;
for (int i = 1; i <= n; i ++)
cin >> a[i], sum[i] = sum[i - 1] + a[i];
seg1.V = n;
seg2.V = sum[n];
seg1.modify (1, 0, n, 0, Line (0, 0));
seg2.modify (1, 0, n, 0, Line (0, 0));
for (int i = 1; i <= n; i ++) {
int l = segmx.query (1, 0, n, 0, a[i]);
int r = ! a[i] ? i : segmx.query (1, 0, n, 0, a[i] - 1);
segmx.modify (1, 0, n, a[i], i);
while (l < r) {
int v = segmx.find (1, 0, n, r - 1);
int pos = segmx.query (1, 0, n, 0, v);
seg2.modify (1, 0, n, pos, Line (v, seg1.query (1, 0, n, pos, r - 1, v)));
r = pos;
}
f[i] = seg2.query (1, 0, n, max (0, i - K), i - 1, sum[i]);
l = max (0, i - K);
int v = segmx.find (1, 0, n, l - 1);
r = ! v ? i : segmx.query (1, 0, n, 0, v - 1);
if (l < r) f[i] = max (f[i], 1ll * v * sum[i] + seg1.query (1, 0, n, l, r - 1, v));
seg1.modify (1, 0, n, i, Line (-sum[i], f[i]));
seg2.modify (1, 0, n, segmx.query (1, 0, n, 0, 0), Line (0, f[i]));
}
cout << f[n];
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 255472kb
input:
5 3 3 4 0 0 3
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: 0
Accepted
time: 24ms
memory: 255400kb
input:
8 4 0 1 2 0 3 1 4 1
output:
26
result:
ok 1 number(s): "26"
Test #3:
score: 0
Accepted
time: 0ms
memory: 254208kb
input:
10 5 0 2 0 1 2 1 0 2 2 1
output:
33
result:
ok 1 number(s): "33"
Test #4:
score: 0
Accepted
time: 16ms
memory: 253888kb
input:
20 10 3 1 3 2 3 3 0 1 3 0 2 3 3 3 3 1 3 0 0 3
output:
160
result:
ok 1 number(s): "160"
Test #5:
score: 0
Accepted
time: 8ms
memory: 254528kb
input:
30 10 14 15 10 1 14 1 8 0 12 8 6 15 1 8 9 12 15 10 11 12 7 10 10 3 3 10 8 14 13 13
output:
172
result:
ok 1 number(s): "172"
Test #6:
score: 0
Accepted
time: 8ms
memory: 254768kb
input:
40 3 0 4 2 4 3 1 5 5 2 3 4 2 1 1 1 5 5 4 1 3 3 0 1 0 2 0 1 4 2 1 5 3 0 4 0 0 0 5 3 3
output:
51
result:
ok 1 number(s): "51"
Test #7:
score: 0
Accepted
time: 7ms
memory: 254188kb
input:
50 20 29 6 30 26 8 11 22 26 24 8 30 25 19 12 28 19 28 4 13 9 2 23 30 15 21 5 30 5 19 17 25 29 2 28 20 16 0 4 26 23 22 30 3 25 29 5 29 24 11 27
output:
378
result:
ok 1 number(s): "378"
Test #8:
score: 0
Accepted
time: 8ms
memory: 253648kb
input:
80 15 2 13 20 11 12 10 19 17 3 7 10 2 14 11 9 17 19 11 17 15 10 18 11 11 14 5 20 8 8 12 13 17 14 19 11 20 13 2 12 2 19 12 6 7 3 4 11 16 1 12 4 16 17 4 1 2 5 11 17 12 13 7 8 12 2 4 15 20 18 1 1 13 1 14 6 5 20 12 12 11
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 11ms
memory: 254852kb
input:
100 30 41 50 33 22 1 34 7 14 31 44 46 49 49 23 33 12 9 41 25 23 22 1 49 45 45 8 10 49 37 23 48 17 32 44 38 21 29 27 23 27 47 44 6 12 7 2 18 12 9 43 20 26 26 8 14 25 18 48 2 41 49 7 48 38 10 45 34 27 17 12 1 19 9 29 50 13 25 21 9 13 26 15 6 9 5 13 47 30 26 17 40 0 21 6 25 24 22 31 43 16
output:
1308
result:
ok 1 number(s): "1308"
Test #10:
score: 0
Accepted
time: 3ms
memory: 255076kb
input:
200 30 1 26 8 2 6 36 43 49 15 48 39 7 12 18 28 46 13 6 24 17 43 44 31 17 30 5 40 19 13 24 26 1 23 39 34 29 28 2 22 23 32 21 32 5 38 11 18 10 15 14 16 7 40 40 35 30 8 3 46 25 36 50 13 37 16 42 39 9 24 5 8 2 15 17 24 35 39 26 5 24 39 23 47 17 23 49 21 30 36 46 26 15 0 24 23 25 12 16 12 18 42 30 20 0 5...
output:
3389
result:
ok 1 number(s): "3389"
Test #11:
score: 0
Accepted
time: 12ms
memory: 254328kb
input:
300 30 39 28 33 6 10 36 27 31 1 1 9 41 27 39 48 30 43 49 0 11 39 36 15 40 43 28 18 15 17 23 4 9 37 32 5 34 3 4 45 44 18 24 6 23 18 21 40 7 18 38 35 14 5 44 4 10 25 34 14 8 23 43 28 11 22 13 44 16 30 49 40 13 21 32 50 30 29 31 27 35 1 30 10 49 42 33 46 30 47 48 13 5 5 41 22 3 26 26 33 20 34 41 46 27 ...
output:
6636
result:
ok 1 number(s): "6636"
Test #12:
score: 0
Accepted
time: 15ms
memory: 254984kb
input:
400 30 25 30 7 36 38 37 10 15 37 6 4 49 42 34 43 13 46 40 1 6 35 29 50 13 30 23 48 12 43 23 32 44 28 28 1 41 2 31 44 40 5 1 6 17 50 5 40 5 48 36 32 47 20 24 25 42 17 40 8 43 9 10 43 34 30 36 48 48 37 18 21 23 26 20 24 2 44 10 22 46 38 12 50 4 9 17 19 30 6 25 1 20 33 33 21 6 15 11 27 22 2 25 22 30 8 ...
output:
5312
result:
ok 1 number(s): "5312"
Test #13:
score: 0
Accepted
time: 12ms
memory: 255672kb
input:
500 30 11 7 6 40 43 14 47 49 22 9 25 32 6 4 12 48 25 31 2 26 30 46 10 36 43 46 2 34 45 48 11 28 43 22 47 47 1 32 41 36 41 3 31 8 31 14 12 2 2 8 0 30 34 5 46 46 6 20 25 27 46 3 34 8 36 33 27 4 19 10 3 32 33 9 49 24 9 15 18 6 0 20 13 11 28 1 18 30 18 4 12 34 39 50 20 35 30 47 46 24 46 36 49 34 21 10 7...
output:
9118
result:
ok 1 number(s): "9118"
Test #14:
score: 0
Accepted
time: 27ms
memory: 254648kb
input:
600 30 49 8 31 19 46 14 31 32 33 39 20 15 46 25 6 32 2 48 28 20 26 39 44 9 5 43 31 30 23 47 39 10 33 42 44 3 26 7 15 6 28 31 5 2 11 24 11 1 6 6 21 10 25 36 16 26 23 27 19 10 33 47 49 7 43 5 32 37 24 3 9 17 39 49 24 20 50 20 15 18 12 27 3 43 46 36 43 31 28 32 50 50 44 43 19 13 20 6 15 26 14 45 25 11 ...
output:
9497
result:
ok 1 number(s): "9497"
Test #15:
score: 0
Accepted
time: 32ms
memory: 254464kb
input:
700 200 190 11 82 65 81 32 130 4 124 52 155 181 166 29 44 49 187 134 155 130 127 17 76 156 59 155 171 194 110 2 102 122 48 191 31 25 83 154 184 56 38 175 50 190 162 191 116 198 170 173 160 177 184 194 195 64 120 27 154 192 96 160 183 196 76 109 15 81 9 189 120 55 42 17 192 20 100 53 29 197 181 152 1...
output:
142372
result:
ok 1 number(s): "142372"
Test #16:
score: 0
Accepted
time: 7ms
memory: 254272kb
input:
800 200 197 112 65 12 115 42 97 158 105 122 140 175 154 63 192 103 43 87 11 114 164 35 179 101 171 13 104 179 185 78 96 75 93 19 191 108 136 161 152 183 123 199 99 197 147 185 82 112 6 157 178 180 200 47 95 15 153 71 89 172 182 98 187 19 129 126 59 166 2 75 135 86 64 37 58 64 148 195 45 165 125 115 ...
output:
193511
result:
ok 1 number(s): "193511"
Test #17:
score: 0
Accepted
time: 7ms
memory: 255672kb
input:
900 200 27 187 75 160 123 52 39 137 85 65 149 67 65 122 140 57 101 39 143 200 100 153 57 47 7 172 62 140 34 153 91 4 61 148 51 165 64 92 119 10 183 97 48 2 58 53 48 1 43 117 71 84 115 176 96 192 109 14 124 51 168 137 191 168 182 143 4 50 71 162 75 16 86 158 50 84 120 60 137 158 69 53 32 24 59 94 178...
output:
387825
result:
ok 1 number(s): "387825"
Test #18:
score: 0
Accepted
time: 36ms
memory: 255752kb
input:
1000 500 120 156 148 83 1 52 17 33 164 176 165 3 66 161 99 132 190 83 124 139 172 30 67 87 132 61 36 8 116 128 162 151 166 24 84 160 52 180 80 120 36 82 97 159 0 83 60 45 195 47 186 166 91 191 88 146 167 133 147 38 126 182 82 23 0 31 70 8 77 118 85 50 55 144 56 115 34 58 57 13 89 132 37 6 11 105 187...
output:
1033863
result:
ok 1 number(s): "1033863"
Test #19:
score: 0
Accepted
time: 46ms
memory: 256064kb
input:
2000 200 39 181 151 81 34 229 56 147 86 128 55 47 211 141 215 97 28 16 235 144 172 198 92 48 226 86 113 233 119 81 123 222 129 200 61 21 246 55 6 66 65 2 5 10 109 239 236 164 185 98 3 236 123 21 131 125 46 235 67 83 205 214 243 111 173 99 2 240 159 66 80 211 96 185 167 187 218 38 105 194 199 57 33 1...
output:
399183
result:
ok 1 number(s): "399183"
Test #20:
score: 0
Accepted
time: 60ms
memory: 255488kb
input:
3000 600 92 85 85 10 57 53 30 1 89 14 70 26 72 73 14 70 30 58 50 78 4 75 79 48 73 40 88 92 5 83 21 57 6 16 30 80 9 76 42 81 17 94 24 72 76 67 85 85 17 68 21 1 14 68 41 86 74 53 73 60 30 70 63 47 100 92 45 67 22 14 69 31 26 56 53 30 43 69 62 52 39 10 47 17 72 93 5 65 32 41 69 88 41 2 14 46 81 49 65 1...
output:
14762368
result:
ok 1 number(s): "14762368"
Test #21:
score: 0
Accepted
time: 297ms
memory: 255032kb
input:
4000 100 1073 699 498 1797 203 458 1112 1140 1749 1900 725 1926 579 396 1711 183 1673 300 1551 370 411 1926 1712 1191 411 54 1170 1324 551 860 68 1864 564 684 766 1300 1715 1849 303 1649 1375 1603 1885 605 403 687 1702 500 1801 1173 1842 443 125 405 1711 1951 1692 671 1983 1247 1451 1279 1075 1230 6...
output:
213208
result:
ok 1 number(s): "213208"
Test #22:
score: 0
Accepted
time: 372ms
memory: 256644kb
input:
5000 400 288 870 939 422 710 726 995 841 2 582 912 28 195 718 252 721 488 416 228 56 507 269 967 48 651 108 405 14 430 319 322 236 510 217 290 808 903 699 960 550 305 282 441 667 825 24 474 649 856 171 284 222 401 39 627 443 276 861 759 62 553 945 243 38 439 452 956 159 96 117 301 182 411 902 159 17...
output:
615424
result:
ok 1 number(s): "615424"
Test #23:
score: 0
Accepted
time: 236ms
memory: 255224kb
input:
6000 1000 226 126 99 274 50 247 244 91 70 104 263 208 196 299 211 268 69 76 278 72 80 11 120 172 224 239 53 296 198 20 282 184 9 96 133 214 79 15 201 220 64 282 211 225 250 256 122 9 1 180 280 44 16 62 90 208 102 140 173 70 242 136 235 249 6 23 38 62 135 204 82 227 281 167 96 233 196 97 243 105 117 ...
output:
45326920
result:
ok 1 number(s): "45326920"
Test #24:
score: 0
Accepted
time: 776ms
memory: 256208kb
input:
7000 3000 321 1652 403 108 1343 744 985 327 1395 1330 1752 1681 1246 1709 1726 1087 1982 1493 8 1798 1400 258 228 1486 589 212 227 421 805 1796 1101 1039 406 170 1128 1765 960 1503 563 346 1495 1477 1421 1367 861 1321 1739 1138 84 1001 1277 1026 977 2 54 812 754 572 1881 1229 30 1659 1566 950 1026 1...
output:
36659018
result:
ok 1 number(s): "36659018"
Test #25:
score: 0
Accepted
time: 905ms
memory: 257344kb
input:
8000 150 0 12 10 13 8 6 2 11 5 11 3 18 7 13 1 11 1 8 11 3 15 13 2 10 5 13 14 15 11 9 20 15 12 1 16 12 6 3 7 7 12 6 11 12 20 18 2 16 13 11 12 2 11 19 17 16 4 11 6 6 12 13 16 9 2 6 15 3 8 2 14 5 17 11 11 19 9 4 6 18 3 20 3 5 10 6 5 10 12 13 14 16 4 15 6 10 7 4 7 15 1 19 15 11 16 20 12 13 15 12 7 12 20...
output:
1669500
result:
ok 1 number(s): "1669500"
Test #26:
score: 0
Accepted
time: 739ms
memory: 257436kb
input:
9000 300 163 487 36 261 54 222 344 292 212 127 139 152 235 463 238 36 240 247 125 399 373 159 372 442 461 57 333 12 68 392 152 490 309 403 63 111 426 280 412 219 110 417 314 264 135 180 214 402 249 232 248 81 128 110 29 209 323 187 109 78 213 313 67 201 466 456 485 197 305 27 202 4 50 465 57 300 244...
output:
2644852
result:
ok 1 number(s): "2644852"
Test #27:
score: 0
Accepted
time: 1452ms
memory: 257748kb
input:
10000 2500 60 9 63 25 100 71 100 80 47 69 33 6 40 61 4 14 44 74 21 63 0 46 62 74 81 69 45 16 56 57 50 4 34 24 42 49 0 12 12 77 38 40 58 46 87 67 28 24 9 28 93 86 11 44 17 7 24 100 5 86 3 34 55 36 23 20 22 84 73 79 30 100 45 42 14 39 82 13 93 14 95 23 87 11 85 95 67 49 46 73 40 94 96 51 10 90 60 18 1...
output:
50431320
result:
ok 1 number(s): "50431320"
Test #28:
score: -100
Time Limit Exceeded
input:
20000 13240 1671 652 803 323 143 1942 1718 189 757 1779 1151 1979 1862 475 104 854 945 1548 31 1271 1108 1605 539 852 1434 1030 140 99 909 466 1508 66 366 67 766 1576 1550 771 1387 1745 1576 1246 355 1426 206 1673 1743 1922 987 156 195 654 1309 1982 1757 192 857 1337 59 58 300 1150 1306 1605 1549 17...