QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#451522#7872. 崩坏天际线zqs100 ✓1791ms24652kbC++145.7kb2024-06-23 16:04:552024-06-23 16:04:55

Judging History

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

  • [2024-06-23 16:04:55]
  • 评测
  • 测评结果:100
  • 用时:1791ms
  • 内存:24652kb
  • [2024-06-23 16:04:55]
  • 提交

answer

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>

using std::min; using std::swap;
const int mod = 998244353, B = 230, N = 50005;
inline void add(int &x, const int y) {if ((x += y) >= mod) x -= mod;}
inline int plus(const int x, const int y) {return x + y < mod ? x + y : x + y - mod;}
int al[N], ar[N], op[N], p2[N], a[2 * B + 5], tme[2 * B + 5], n, q, ans;
int bl[2 * B * B + 5], br[2 * B * B + 5], bp[2 * B * B + 5],
cl[2 * B + 5], cr[2 * B + 5], stk[2 * B + 5], cnt;
struct node {int ls, rs, sum, tag;} tr[2500005];
int id[N], pre[N], nxt[N], len[N];
bool vis[N], ban[N];
std::vector<int> vec[50005];
struct RMQ {
	int st[17][50005], Log[50005];
	void clear() {memset(st[0], 0x3f, sizeof st[0]);}
	void set(int x, int v) {st[0][x] = v;}
	void init() {
		for (int i = 2; i <= n; ++ i) Log[i] = Log[i >> 1] + 1;
		for (int i = 1; i <= 15; ++ i)
		for (int j = 1; j + (1 << i) - 1 <= n; ++ j)
			st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
	}
	int query(int l, int r) {
		if (l > r) return q + 1;
		int k = Log[r - l + 1];
		return min(st[k][l], st[k][r - (1 << k) + 1]);
	}
} rmq;
int prob[N], rt1[N], rt2[N], tot;
void spread(int p) {
	if (!tr[p].tag) return;
	int ls = tr[p].ls, rs = tr[p].rs, tmp = tr[p].tag; tr[p].tag = 0;
	if (ls) tr[ls].sum = 1ll * tr[ls].sum * p2[tmp] % mod, tr[ls].tag += tmp;
	if (rs) tr[rs].sum = 1ll * tr[rs].sum * p2[tmp] % mod, tr[rs].tag += tmp;
}
void insert(int &p, int l, int r, int x, int v) {
	if (!p) p = ++ tot, tr[p].ls = tr[p].rs = tr[p].sum = tr[p].tag = 0;
	add(tr[p].sum, v); if (l == r) return;
	int mid = l + r >> 1; spread(p);
	x <= mid ? insert(tr[p].ls, l, mid, x, v) : insert(tr[p].rs, mid + 1, r, x, v);
}
void pushup(int p) {if (p) tr[p].sum = plus(tr[tr[p].ls].sum, tr[tr[p].rs].sum);}
void split(int &x, int &y, int l, int r, int k) {
	if (!x || r <= k) return;
	if (k < l) {y = x, x = 0; return;}
	spread(x);
	int mid = l + r >> 1, z = 0; tr[y = ++ tot].tag = 0;
	if (k <= mid) {
		split(tr[x].ls, z, l, mid, k), tr[y].ls = z, tr[y].rs = tr[x].rs, tr[x].rs = 0;
	} else split(tr[x].rs, z, mid + 1, r, k), tr[y].ls = 0, tr[y].rs = z;
	pushup(x), pushup(y);
}
void query(int p, int l, int r, int x) {
	if (!p) return;
	if (l == r) {ans = (ans + 1ll * abs(x - l) * tr[p].sum) % mod; return;}
	spread(p);
	query(tr[p].ls, l, l + r >> 1, x), query(tr[p].rs, (l + r >> 1) + 1, r, x);
}

void solve(int st) {
	memset(pre, 0, sizeof pre), memset(nxt, 0, sizeof nxt);
	memset(prob, 0, sizeof prob), memset(vis, 0, sizeof vis);
	memset(ban, 0, sizeof ban), rmq.clear();
	for (int i = q; i >= st; -- i) if (op[i] == 2) rmq.set(al[i], i);
	rmq.init(), tot = 0;
	for (int i = 1; i <= n; ++ i) vec[i].clear(), rt1[i] = rt2[i] = 0;
	for (int i = 1; i <= cnt; ++ i) {
		int fst = rmq.query(bl[i] + 1, br[i] - 1);
		if (fst > q) ans = (ans + 1ll * bp[i] * (br[i] - bl[i])) % mod;
		else vec[al[fst]].emplace_back(i);
	}
	for (int i = st; i <= q; ++ i)
		if (op[i] == 2) {if (vis[al[i]]) ban[i] = true; else vis[al[i]] = true;}
	for (int i = 1, j = 0; i <= n; ++ i)
		if (vis[i]) pre[i] = j, nxt[j] = i, len[j] = i - j, j = i;
	pre[0] = nxt[0] = 0;
	for (int i = q; i >= st; -- i) if (op[i] == 2 && !ban[i]) {
		int x = al[i];
		if (pre[x]) nxt[pre[x]] = nxt[x];
		if (nxt[x]) pre[nxt[x]] = pre[x];
	}
	for (int i = st; i <= q; ++ i) if (op[i] == 2 && !ban[i]) {
		int x = al[i], l = pre[x], r = nxt[x];
		if (r) {
			split(rt1[r], rt1[x], 1, n, x - 1), swap(rt1[r], rt1[x]);
			if (rt1[x]) tr[rt1[x]].sum = 1ll * tr[rt1[x]].sum * p2[1] % mod, ++ tr[rt1[x]].tag;
		}
		if (l) {
			split(rt2[l], rt2[x], 1, n, x);
			if (rt2[x]) tr[rt2[x]].sum = 1ll * tr[rt2[x]].sum * p2[1] % mod, ++ tr[rt2[x]].tag;
		}
		prob[x] = (1ll * prob[l] * p2[1] + tr[rt1[x]].sum) % mod;
		prob[l] = (1ll * prob[l] * p2[1] + tr[rt2[x]].sum) % mod;
		for (int j : vec[x]) {
			insert(rt1[x], 1, n, bl[j], 1ll * bp[j] * p2[1] % mod);
			insert(rt2[x], 1, n, br[j], 1ll * bp[j] * p2[1] % mod);
		}
	}
	for (int i = 1; i <= n; ++ i) {
		if (prob[i]) ans = (ans + 1ll * len[i] * prob[i]) % mod;
		if (rt1[i]) query(rt1[i], 1, n, i);
		if (rt2[i]) query(rt2[i], 1, n, i);
	}
}

int main() {
	scanf("%d%d", &n, &q);
	p2[0] = 1, p2[1] = mod + 1 >> 1;
	for (int i = 1; i <= q; ++ i) {
		scanf("%d%d", op + i, al + i); if (op[i] == 1) scanf("%d", ar + i);
	}
	for (int i = 2; i <= q; ++ i) p2[i] = 1ll * p2[1] * p2[i - 1] % mod;
	for (int i = 1; i <= (q + B - 1) / B; ++ i) {
		int st = (i - 1) * B + 1, ed = min(q, i * B), m = 0;
		cnt = 0;
		for (int j = ed; j >= st; -- j) {
			if (op[j] == 2) {
				int pos = m + 1;
				for (int k = 1; k <= m; ++ k)
					if (a[k] > al[j]) {pos = k; break;}
					else if (a[k] == al[j]) {pos = 0, tme[k] = j; break;}
				if (pos) {
					++ m; 
					for (int k = m; k > pos; -- k) a[k] = a[k - 1], tme[k] = tme[k - 1];
					a[pos] = al[j], tme[pos] = j;
				}
			} else {
				int l = m + 1, r = 0;
				for (int k = 1; k <= m; ++ k) if (a[k] > al[j]) {l = k; break;}
				for (int k = m; k; -- k) if (a[k] < ar[j]) {r = k; break;}
				if (l > r) {bl[++ cnt] = al[j], br[cnt] = ar[j], bp[cnt] = 1; continue;}
				for (int k = l, top = 0; k <= r; ++ k) {
					while (top && tme[stk[top]] > tme[k]) -- top;
					stk[++ top] = k, cl[k] = top;
				}
				for (int k = r, top = 0; k >= l; -- k) {
					while (top && tme[stk[top]] > tme[k]) -- top;
					stk[++ top] = k, cr[k] = top;
				}
				for (int k = l; k < r; ++ k)
					bl[++ cnt] = a[k], br[cnt] = a[k + 1], bp[cnt] = p2[cl[k] + cr[k + 1]];
				bl[++ cnt] = al[j], br[cnt] = a[l], bp[cnt] = p2[cr[l]];
				bl[++ cnt] = a[r], br[cnt] = ar[j], bp[cnt] = p2[cl[r]];
			}
		}
		solve(ed + 1);
	}
	printf("%d", ans);
	return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 2ms
memory: 12360kb

input:

500 500
1 119 258
2 134
2 417
2 176
2 61
2 60
2 110
1 335 336
1 96 111
2 202
1 138 344
2 358
2 134
1 29 54
1 73 381
1 179 495
2 490
2 418
2 186
2 183
1 168 340
2 78
1 15 27
2 373
1 245 498
1 372 495
2 244
2 63
1 174 490
2 282
2 417
1 272 408
1 109 134
2 303
2 345
1 238 401
1 36 480
1 21 483
2 10
1 3...

output:

855279801

result:

ok single line: '855279801'

Test #2:

score: 0
Accepted
time: 2ms
memory: 12400kb

input:

495 466
1 35 393
2 236
1 4 335
2 455
1 36 470
1 23 61
2 195
2 109
2 451
1 282 491
2 238
2 117
2 468
1 2 60
1 439 487
2 238
1 209 294
2 321
2 309
1 113 183
2 409
2 87
2 130
2 124
2 176
2 448
2 379
1 181 446
2 146
2 450
1 171 423
2 355
2 332
1 123 387
1 151 269
1 17 417
2 122
1 324 494
1 265 439
2 225...

output:

294468977

result:

ok single line: '294468977'

Test #3:

score: 0
Accepted
time: 0ms
memory: 12096kb

input:

441 467
2 180
1 51 344
2 180
1 16 345
1 39 419
1 64 432
2 176
1 35 372
2 426
1 8 415
1 1 439
1 17 430
2 433
1 89 369
1 83 353
2 292
1 1 421
1 63 430
1 33 345
1 69 421
1 49 373
1 77 343
1 24 393
1 90 375
1 8 425
2 322
2 61
2 112
2 209
1 39 406
1 12 426
1 29 430
1 50 374
1 47 394
1 9 387
2 234
1 19 35...

output:

526117259

result:

ok single line: '526117259'

Test #4:

score: 0
Accepted
time: 2ms
memory: 8504kb

input:

500 500
2 442
1 12 414
1 40 435
2 138
1 79 448
1 16 464
2 163
1 94 492
2 97
2 335
1 7 452
1 25 474
1 78 442
2 286
1 93 430
1 78 438
2 469
2 354
2 270
2 292
2 108
2 301
1 100 480
2 258
1 17 487
2 2
2 409
2 385
2 338
1 83 454
1 41 490
1 95 475
1 43 442
1 66 445
2 406
2 168
1 10 406
2 330
2 20
1 90 491...

output:

810270061

result:

ok single line: '810270061'

Test #5:

score: 0
Accepted
time: 0ms
memory: 12424kb

input:

500 500
1 29 407
1 89 480
1 31 497
1 28 494
1 21 492
1 91 465
1 13 467
1 89 425
1 22 444
1 20 430
1 48 445
1 33 441
1 61 435
1 69 427
1 89 485
1 90 446
1 23 488
1 6 424
1 76 425
1 36 460
1 16 421
1 20 500
1 3 487
1 99 481
1 53 412
1 96 456
1 39 436
1 28 436
1 4 409
1 9 486
1 22 484
1 88 413
1 26 467...

output:

419428992

result:

ok single line: '419428992'

Test #6:

score: 0
Accepted
time: 2ms
memory: 12572kb

input:

500 500
1 85 442
1 20 473
1 10 441
1 31 426
1 95 478
1 60 454
1 54 491
1 97 464
1 14 443
1 88 474
1 28 462
1 97 410
1 99 496
1 96 493
1 62 479
1 12 466
1 64 471
1 43 490
1 50 411
1 85 448
1 48 433
1 30 456
1 39 462
1 46 409
1 63 494
1 39 409
1 36 436
1 27 463
1 37 498
1 69 464
1 8 441
1 99 436
1 84 ...

output:

519347055

result:

ok single line: '519347055'

Subtask #2:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #7:

score: 20
Accepted
time: 20ms
memory: 9348kb

input:

5000 5000
2 2254
2 4832
2 208
1 335 3080
2 481
1 527 3659
1 2645 3803
1 855 3544
2 3824
2 347
1 1567 4426
1 2184 4493
2 142
2 2451
1 995 4170
2 576
2 999
2 2726
1 278 3540
2 3218
1 922 3302
2 3253
2 4161
2 4505
1 4201 4534
1 1827 3540
2 3241
2 1909
2 2667
1 723 2453
2 3123
1 1017 4791
1 2953 3384
1 ...

output:

275175220

result:

ok single line: '275175220'

Test #8:

score: 0
Accepted
time: 17ms
memory: 12644kb

input:

4753 4704
1 589 2183
1 922 2210
2 2885
2 171
2 1597
2 3601
1 1906 4730
1 411 3615
2 1665
1 87 801
2 3525
2 2426
2 2723
1 323 4345
2 3950
2 460
2 4165
1 1156 2642
1 1490 3965
1 329 4081
1 1206 2077
2 4216
1 996 2254
2 2219
2 1035
2 4074
2 714
1 952 2726
2 3097
2 409
1 3320 4713
2 4061
1 1765 2040
1 2...

output:

840227126

result:

ok single line: '840227126'

Test #9:

score: 0
Accepted
time: 11ms
memory: 14640kb

input:

4141 4610
2 3761
2 2872
1 334 3247
1 273 3914
1 307 3651
1 607 4105
1 458 3269
1 270 3782
2 311
1 533 3332
2 2495
1 991 3573
1 376 3593
1 239 3682
1 259 3350
1 213 3380
2 1904
1 591 3512
1 845 3785
1 189 3335
1 817 3362
1 335 3288
2 3633
1 747 3586
2 4062
2 3812
1 487 3333
1 740 4002
1 847 3937
1 53...

output:

597472157

result:

ok single line: '597472157'

Test #10:

score: 0
Accepted
time: 21ms
memory: 14752kb

input:

5000 5000
2 2864
1 473 4676
2 858
2 2672
2 4473
2 800
2 3259
2 470
2 3859
2 2228
1 491 4536
1 700 4378
2 498
1 769 4837
1 80 4861
1 109 4201
1 908 4094
1 9 4706
2 1017
2 737
2 4155
1 270 4290
2 4434
2 1867
1 148 4119
1 299 4194
2 4076
2 1863
2 1570
2 4855
1 1000 4834
1 637 4827
2 1961
2 4518
1 811 4...

output:

251906928

result:

ok single line: '251906928'

Test #11:

score: 0
Accepted
time: 10ms
memory: 12716kb

input:

5000 5000
1 327 4388
1 768 4973
1 438 4243
1 288 4244
1 105 4460
1 862 4894
1 125 4611
1 934 4115
1 631 4349
1 635 4088
1 250 4629
1 873 4204
1 977 4296
1 391 4821
1 107 4589
1 86 4810
1 615 4072
1 221 4113
1 745 4771
1 806 4983
1 675 4334
1 709 4428
1 587 4180
1 494 4949
1 904 4253
1 901 4527
1 717...

output:

845230417

result:

ok single line: '845230417'

Test #12:

score: 0
Accepted
time: 12ms
memory: 12896kb

input:

5000 5000
1 902 4097
1 263 4218
1 502 4305
1 798 4433
1 392 4689
1 479 4006
1 518 4269
1 764 4295
1 48 4834
1 966 4574
1 374 4970
1 950 4925
1 54 4860
1 987 4144
1 448 4504
1 329 4838
1 734 4807
1 403 4387
1 275 4396
1 731 4769
1 206 4348
1 282 4258
1 676 4956
1 274 4943
1 892 4146
1 337 4962
1 798 ...

output:

678724707

result:

ok single line: '678724707'

Subtask #3:

score: 40
Accepted

Test #13:

score: 40
Accepted
time: 1199ms
memory: 18284kb

input:

50000 50000
1 24367 33007
1 14396 42256
1 6375 22327
1 7892 42501
1 10100 37998
1 6284 48524
1 7357 18164
1 16200 46424
1 18972 34131
1 16849 32591
1 1917 3018
1 19897 30272
1 45044 45753
1 18999 25448
1 5167 31033
1 6182 35335
1 7270 37270
1 12651 39965
1 28896 38022
1 13853 35426
1 35516 48244
1 1...

output:

733099543

result:

ok single line: '733099543'

Test #14:

score: 0
Accepted
time: 920ms
memory: 19476kb

input:

49951 43686
1 21796 23464
1 29304 46959
1 5034 41719
1 7779 35334
1 27566 36486
1 20347 26165
1 12508 30387
1 18363 20335
1 8540 21417
1 5728 49086
1 46038 47603
1 10371 15910
1 27293 43572
1 18915 45279
1 7388 48342
1 6802 43746
1 4361 40049
1 41177 43375
1 23287 48354
1 37097 41733
1 2406 11638
1 ...

output:

792296531

result:

ok single line: '792296531'

Test #15:

score: 0
Accepted
time: 417ms
memory: 15824kb

input:

49914 43874
1 8935 40963
1 4425 44317
1 1769 45855
1 2436 40257
1 1778 47216
1 383 42149
1 5398 40732
1 1079 43346
1 6578 41660
1 9689 45985
1 6131 42681
1 8862 47431
1 3979 46189
1 6456 43485
1 2028 46574
1 3802 47787
1 6990 41659
1 9221 41204
1 2271 43554
1 8018 45280
1 9344 43917
1 6623 41152
1 7...

output:

831211412

result:

ok single line: '831211412'

Test #16:

score: 0
Accepted
time: 610ms
memory: 18244kb

input:

50000 50000
1 1310 49344
1 5755 44255
1 3582 41465
1 6800 42160
1 1651 44584
1 7967 44410
1 3116 48795
1 1855 41120
1 27 42294
1 2455 49629
1 4196 42487
1 7070 44542
1 136 42053
1 5715 44222
1 8794 43115
1 4048 45579
1 635 46703
1 9246 41055
1 3678 41276
1 4871 41715
1 1659 44679
1 1639 46392
1 2479...

output:

316801136

result:

ok single line: '316801136'

Test #17:

score: 0
Accepted
time: 512ms
memory: 21520kb

input:

50000 50000
1 8731 40028
1 6575 43815
1 9558 42476
1 7269 47567
1 6597 45567
1 7753 49129
1 9892 47319
1 9438 45710
1 8688 46209
1 75 43653
1 8918 44467
1 2751 43343
1 4433 45172
1 8062 40732
1 3342 41158
1 615 45475
1 7497 44843
1 9201 48262
1 3063 44796
1 9294 48709
1 382 46129
1 5935 48889
1 1195...

output:

680677335

result:

ok single line: '680677335'

Test #18:

score: 0
Accepted
time: 847ms
memory: 21284kb

input:

50000 50000
1 5934 20406
1 21982 32375
1 7064 32616
1 28419 47337
1 28379 31201
1 40915 47773
1 14903 35558
1 2825 43481
1 28451 29178
1 4872 24238
1 5487 6527
1 33950 35231
1 6301 27246
1 3825 16238
1 3823 46254
1 10988 36002
1 6447 8234
1 4758 20500
1 4816 33750
1 3332 3743
1 723 25813
1 6797 4955...

output:

211908161

result:

ok single line: '211908161'

Subtask #4:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #19:

score: 30
Accepted
time: 1410ms
memory: 22476kb

input:

50000 50000
1 23820 35205
1 23204 28152
1 10968 38077
2 26347
1 34065 43744
2 6956
1 12386 31941
1 5586 8700
1 37329 37421
1 13872 49853
1 10054 40143
2 9721
1 3312 36213
1 11745 48452
2 27741
2 37848
2 2566
2 9714
1 38322 48081
2 25675
1 28940 35759
2 11908
1 21501 22242
1 22858 23827
1 13837 25563...

output:

963178931

result:

ok single line: '963178931'

Test #20:

score: 0
Accepted
time: 1210ms
memory: 21388kb

input:

49844 49196
1 14456 32911
1 25807 25848
1 36273 38462
2 906
2 11834
2 1552
2 24305
1 25916 28701
2 15959
2 36578
1 4325 48457
1 25678 44301
2 9794
1 11656 20160
2 22873
2 44228
1 29465 40920
2 24618
2 5092
2 47096
1 8617 18389
1 35678 41207
1 12614 16730
2 23299
2 240
1 1980 46841
2 39602
1 2700 217...

output:

720301477

result:

ok single line: '720301477'

Test #21:

score: 0
Accepted
time: 654ms
memory: 19524kb

input:

40208 47419
1 3878 39147
2 40063
1 5302 30782
1 5676 36573
1 3071 31029
2 37839
1 19 34805
1 8302 36156
2 3219
1 3855 38334
2 28443
2 32961
1 7085 30246
2 26657
1 1197 39431
1 6522 37149
2 2160
1 7638 34260
1 7938 36825
2 31484
2 15343
1 4546 34945
1 8836 39829
2 14331
1 8469 34573
2 38079
1 2851 36...

output:

479455278

result:

ok single line: '479455278'

Test #22:

score: 0
Accepted
time: 1317ms
memory: 24652kb

input:

50000 50000
2 13550
2 36223
2 43206
1 5510 47597
2 6104
2 25632
1 9207 49739
1 8081 48987
1 5850 49093
1 5202 40432
2 44451
1 4973 41354
2 47071
2 37601
1 22 47601
1 2915 47643
2 9535
2 30503
2 37084
1 9914 43003
2 36565
1 6144 45818
1 8675 48820
1 406 45803
2 21625
2 18503
2 34530
1 7996 46583
1 66...

output:

749830221

result:

ok single line: '749830221'

Test #23:

score: 0
Accepted
time: 1791ms
memory: 23228kb

input:

50000 50000
2 13683
2 21410
2 44457
2 43166
2 12830
1 17939 27321
2 36727
1 27602 40953
2 18534
2 15927
2 38517
2 49434
2 41945
2 43511
2 2024
2 23862
2 24358
2 20120
2 28683
2 7467
2 35825
2 1214
2 46879
2 20156
2 6592
2 32224
2 181
1 27585 35166
2 6322
2 21685
2 46456
2 32309
2 10167
1 4022 29619
...

output:

407055283

result:

ok single line: '407055283'

Test #24:

score: 0
Accepted
time: 997ms
memory: 21420kb

input:

50000 50000
1 3717 40186
1 9852 44874
1 3429 45225
1 6774 49357
1 2761 49086
1 4497 41804
1 6653 45983
1 8605 45746
1 3439 45258
1 4871 45925
1 8952 49447
1 4846 42095
1 4949 48806
1 5032 49881
1 9094 47754
1 6003 43829
1 1665 41735
1 2596 49349
1 4544 42951
1 8987 47280
1 4031 42116
1 9586 48466
1 ...

output:

257719259

result:

ok single line: '257719259'