QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

你现在查看的是最新测评结果

[2024-01-22 21:34:47]
评测

测评结果：TL
用时：1452ms
内存：257748kb

查看

[2024-01-22 21:34:46]
提交

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];
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 8ms

memory: 255472kb

input:

5 3
3 4 0 0 3

output:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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:

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...