QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142038#4918. 染色Mao_Master10 583ms103352kbC++145.1kb2023-08-18 11:45:422023-08-18 11:45:43

Judging History

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

  • [2023-08-18 11:45:43]
  • 评测
  • 测评结果:10
  • 用时:583ms
  • 内存:103352kb
  • [2023-08-18 11:45:42]
  • 提交

answer

#include <cstdio>
#include <algorithm>
#include <set>
#define ull unsigned long long
using namespace std;
const int N = 3e5 + 5;
int n,m,Q;
int a[1001][1001];
ull val[1001];
struct seg {
	int id[4001];
	void build(int now , int l , int r) {
		if(l == r) {id[now] = l;return;}
		int mid = l + r >> 1;
		build(now << 1 , l , mid);
		build(now << 1 | 1 , mid + 1 , r);
		id[now] = l;
	}
	void update(int now , int l , int r , int x , int val) {
		if(l == r) {
			if(val == 1)id[now] = m + 1;
			else id[now] = l;
			return;
		}
		int mid = l + r >> 1;
		if(x <= mid)update(now << 1 , l , mid , x , val);
		else update(now << 1 | 1 , mid + 1 , r , x ,val);
		id[now] = min(id[now << 1] , id[now << 1 | 1]);
	}
}T[1001];
struct question {
	int opt , l , r , x;
	ull v;
}q[N];
struct seg2 {
	int mn[N << 2],cnt[N << 2],in[N << 2][11];
	bool add[N << 2][11],del[N << 2][11];
	ull tag[N << 2],sum[N << 2];
	void build(int now , int l , int r) {
		mn[now] = 1;cnt[now] = r - l + 1;
		if(l == r)return;
		int mid = l + r >> 1;
		build(now << 1 , l , mid);
		build(now << 1 | 1 , mid + 1 , r);
	}
	void pushdown(int now , int l , int r) {
		int mid = l + r >> 1 , ls = now << 1 , rs = now << 1 | 1;
		mn[ls] = mn[rs] = 11;cnt[ls] = cnt[rs] = r - l + 1;
		for(int i = 1;i <= 10;++i)
			if(add[now][i]) {
				in[ls][i] = mid - l + 1;add[ls][i] = 1;del[ls][i] = 0;
				in[rs][i] = r - mid;add[rs][i] = 1;del[ls][i] = 0;
				add[now][i] = 0;
			} else if(del[now][i]) {
				in[ls][i] = 0;del[ls][i] = 1;add[ls][i] = 0;
				in[rs][i] = 0;del[rs][i] = 1;add[rs][i] = 0;
				del[now][i] = 0;
			}
		for(int i = 1;i <= 10;++i) {
			if(in[ls][i] < mid - l + 1 && mn[ls] > i)
				mn[ls] = i , cnt[ls] = mid - l + 1 - in[ls][i];
			if(in[rs][i] < r - mid && mn[rs] > i)
				mn[rs] = i , cnt[rs] = r - mid - in[rs][i];
		}
		if(mn[ls] == mn[now])tag[ls] += tag[now] , sum[ls] += tag[now] * cnt[ls];
		if(mn[rs] == mn[now])tag[rs] += tag[now] , sum[rs] += tag[now] * cnt[rs];
		tag[now] = 0;
	}
	void pushup(int now , int l , int r) {
		int mid = l + r >> 1 , ls = now << 1 , rs = now << 1 | 1;
		mn[now] = 11;cnt[now] = r - l + 1;
		for(int i = 1;i <= 10;++i)in[now][i] = in[ls][i] + in[rs][i];
		for(int i = 1;i <= 10;++i)
			if(in[now][i] < r - l + 1)
				{mn[now] = i;cnt[now] = r - l + 1 - in[now][i];break;}
		sum[now] = sum[ls] + sum[rs];
	}
	void update(int now , int l , int r , int x , int y , int val , int type) {
//		printf("now = %d l = %d r = %d\n",now,l,r);
		if(l != r)pushdown(now , l , r);
		if(x <= l && r <= y) {
			in[now][val] = r - l + 1;
			if(type == 1)add[now][val] = 1 , del[now][val] = 0;
			else del[now][val] = 1 , in[now][val] = 0;
			mn[now] == 11;
			for(int i = 1;i <= 10;++i)
				if(in[now][i] < r - l + 1)
					{mn[now] = i;cnt[now] = r - l + 1 - in[now][i];}
			return;
		}
		int mid = l + r >> 1;
		if(x <= mid)update(now << 1 , l , mid , x , y , val , type);
		if(mid < y)update(now << 1 | 1 , mid + 1 , r , x , y , val , type);
		pushup(now , l , r);
	}
	void modify(int now , int l , int r , int x , int y , ull val) {
		if(l != r)pushdown(now , l , r);
		if(x <= l && r <= y) {
			tag[now] += val;
			sum[now] += cnt[now] * val;
			return;
		}
		int mid = l + r >> 1;
		if(x <= mid)modify(now << 1 , l , mid , x , y , val);
		if(mid < y)modify(now << 1 | 1 , mid + 1 , r , x , y , val);
		pushup(now , l , r);
	}
	ull query(int now , int l , int r , int x , int y) {
		if(l != r)pushdown(now , l , r);
		if(x <= l && r <= y)return sum[now];
		int mid = l + r >> 1;
		ull res = 0;
		if(x <= mid)res = query(now << 1 , l , mid , x , y);
		if(mid < y)res += query(now << 1 | 1 , mid + 1 , r , x , y);
		pushup(now , l , r);
		return res;
	}
}T0;
int main() {
	scanf("%d%d",&n,&m);
	Q = m;
	for(int i = 1;i <= Q;++i) {
		scanf("%d%d%d",&q[i].opt,&q[i].l,&q[i].r);
		if(q[i].opt == 1 || q[i].opt == 2)scanf("%d",&q[i].x);
		else if(q[i].opt == 3)scanf("%llu",&q[i].v);
	}
	if(n <= 1000 && m <= 1000) {
		for(int i = 1;i <= n;++i)T[i].build(1 , 1 , m);
		for(int j = 1;j <= Q;++j) {
			int opt = q[j].opt;
			int l = q[j].l , r = q[j].r , x = q[j].x;
			ull v = q[j].v;
			if(opt == 1 || opt == 2) {
				for(int i = l;i <= r;++i)
					T[i].update(1 , 1 , m , x , (opt == 1) ? 1 : 0);
			}
			if(opt == 3) {
				int mn = m + 1;
				for(int i = l;i <= r;++i)
					if(T[i].id[1] < mn)mn = T[i].id[1];
				for(int i = l;i <= r;++i)
					if(T[i].id[1] == mn)val[i] += v;
			}
			if(opt == 4) {
				ull ans = 0;
				for(int i = l;i <= r;++i)ans += val[i];
				printf("%llu\n",ans);
			}
		}
		return 0;
	}
	bool task2 = 1;
	for(int i = 1;i <= Q;++i)
		if(q[i].x > 10) {task2 = 0;break;}
	if(task2) {
		T0.build(1 , 1 , n);
		for(int i = 1;i <= Q;++i) {
			int opt = q[i].opt;
			int l = q[i].l , r = q[i].r , x = q[i].x;
			ull v = q[i].v;
			if(opt == 1 || opt == 2)T0.update(1 , 1 , n , l , r , x , (opt == 1) ? 1 : 0);
			else if(opt == 3)T0.modify(1 , 1 , n , l , r , v);
				else printf("%llu\n",T0.query(1 , 1 , n , l , r));
//			printf("cnt[1] = %d %d %d\n",T0.cnt[1],T0.mn[1],T0.sum[1]);
		}
		return 0;
	}
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 5ms
memory: 20044kb

input:

1000 1000
3 722 914 2141556875752121755
3 323 347 6433743606947304931
2 142 206 439
2 117 840 195
2 127 502 56
3 168 707 15142638115094015116
4 190 257
2 88 976 475
1 319 867 351
1 682 889 409
2 406 446 196
3 28 35 4899387534800369959
2 291 546 150
1 528 617 128
1 58 122 251
2 381 400 276
4 510 958
...

output:

15128467772367689008
17361914246216994339
5483226026482017320
3033562207293358603
2081407883485577238
7431958406282818646
4664359672511637691
8517692808398202534
17884251128335023776
3389445997760709607
15161173652136060523
17246899135664170339
16659472119973467421
5618344994614112283
92650283427734...

result:

ok 288 tokens

Test #2:

score: 0
Accepted
time: 4ms
memory: 22044kb

input:

1000 1000
1 538 681 44
2 112 540 10
1 160 191 28
1 276 867 1
4 118 419
4 62 209
1 575 884 37
1 783 895 45
4 342 410
2 545 870 16
1 273 501 11
3 258 352 13270291835335737625
3 490 514 5208698592597571883
2 629 865 43
3 966 981 14431353048791951405
1 290 809 16
4 468 843
1 607 875 26
2 177 521 6
4 176...

output:

0
0
0
1090256298972435763
147836376791542005
2987455658418197192
17393388322162025577
0
15463425577465259729
5603739312727078592
9162759280430770517
5734982725161877299
17209386033616770563
4838930779004365643
849737692109005723
6426101344117061130
5419322161439603233
5062725202245147693
71096115354...

result:

ok 245 tokens

Test #3:

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

input:

1000 1000
3 99 666 17220025026447219412
4 5 483
3 749 845 16031212477837693538
3 133 609 17502764194597679430
1 20 226 5
4 251 561
4 633 824
4 200 311
4 519 771
1 441 468 4
1 143 922 2
3 125 229 12754000280540900298
1 498 505 6
1 363 450 3
2 271 554 3
1 114 704 4
2 120 814 2
3 690 982 45445988286128...

output:

7328512720450443476
7442164624875844502
14518824065043662144
15136137278022830944
9027578627713658176
14666047547670987011
9573739028108360400
15993305979184887208
14884581396130778517
17761136731703624839
13312122318790827838
14347674975080853967
17128890277609978434
9773479657321740818
15378095570...

result:

ok 256 tokens

Test #4:

score: 0
Accepted
time: 9ms
memory: 19824kb

input:

1000 1000
3 331 336 13313883338135403138
2 34 521 1
1 207 917 1
2 293 636 1
1 10 687 1
2 41 872 1
1 355 758 1
1 288 842 1
3 400 783 5775690383446019013
4 314 322
2 304 613 1
2 826 891 1
2 202 822 1
4 548 564
4 116 797
2 19 741 1
3 682 909 6383131735642614258
1 236 239 1
3 540 587 8352069600659472359...

output:

0
5953016150034565141
10352142132099319436
6096323733974212364
12116874695872864409
15347176369296045030
5941262347742323458
3620424356881155419
10127217571760838974
5461268237196718849
17374108689525300602
10962054618902200654
10589539750496832325
18040788904369214946
4431085881313941227
1086737541...

result:

ok 245 tokens

Test #5:

score: 0
Accepted
time: 1ms
memory: 19496kb

input:

1000 1000
4 508 569
3 464 647 9626512068323288850
1 261 912 260
4 11 44
4 277 438
4 284 694
2 58 226 212
1 457 503 39
2 706 712 21
4 284 619
1 512 792 423
2 157 161 53
4 277 536
1 366 980 414
1 316 876 190
3 371 886 9029081672906636708
4 194 444
2 745 753 461
3 213 319 890290010596372158
2 753 762 3...

output:

0
0
0
390789495368193264
7549612687959379704
1759106186637124642
4069257141547258216
0
17049456214560332466
12608950793396043246
15542879177249956503
5268553984485336740
3347535289204500833
1283339644428090794
900030301309717320
10617803241693535373
14165237887531480080
7981622196338660662
108862472...

result:

ok 249 tokens

Test #6:

score: 0
Accepted
time: 8ms
memory: 18328kb

input:

1000 1000
3 129 542 13655472611747991961
4 511 790
2 427 432 24
4 297 777
3 42 429 12538231273219784506
2 599 608 39
3 527 566 15984446643208694087
2 205 211 1
3 601 694 12523292657204424213
3 545 831 15344770091989840452
1 602 989 37
1 53 385 37
4 682 969
3 543 721 5478413773432004467
1 56 745 34
3...

output:

12700009880616055584
1938841074867628294
11101356538763217641
10137253135833169997
13873622059376146753
13337075822234643821
9115529121094266177
7669597812731439884
7653582597306726684
16408805096415770957
5310328737375184018
10833975347168974529
3499327095010911697
4157942280079245663
1226136409211...

result:

ok 237 tokens

Test #7:

score: 0
Accepted
time: 1ms
memory: 18124kb

input:

1000 1000
2 235 237 1
3 293 925 11446750964413798601
1 299 374 3
4 663 909
3 11 599 10235863487659693663
2 68 71 10
1 354 730 5
2 716 719 1
1 492 636 6
2 653 657 6
1 383 436 3
4 25 151
4 63 940
4 375 432
4 271 700
1 42 349 4
1 282 760 2
1 277 993 5
4 230 883
2 353 357 5
3 193 326 3721636915624045074...

output:

4995644932646857199
8682577773112482081
14198642487599396424
3213041208013041424
13539808857214091375
761700240778104149
303442926722239461
3516102455933096238
57413777171872180
7755609655116170430
4422876140281257386
5188821315335992835
12241893756112962715
16177149822898993950
340672744116294775
1...

result:

ok 262 tokens

Test #8:

score: 0
Accepted
time: 4ms
memory: 18756kb

input:

1000 1000
2 677 685 1
3 323 762 12895483491686386027
3 298 384 18175344572520049422
4 502 504
2 82 84 5
4 366 888
4 446 447
1 215 667 2
4 74 288
4 713 832
1 647 758 6
2 814 823 2
4 335 545
3 549 653 4845209895729503532
3 727 749 2017173238814894361
3 106 331 7491311112690514667
4 383 640
1 306 501 3...

output:

1792962327640054849
4602247259348913401
7344222909663220438
0
17584876078194546406
14152406924757806061
9115461223074385858
16394226226497421375
11880805806882569475
6738114177990764802
6873497294390714416
4519670768317052046
12682237596341027497
12763260220853210949
6314086074882193678
149826222253...

result:

ok 241 tokens

Test #9:

score: 0
Accepted
time: 4ms
memory: 19532kb

input:

1000 1000
1 34 37 5
3 126 206 14727478235725604056
3 654 744 18255408097680139947
1 480 887 3
2 949 957 12
2 73 73 4
2 475 479 13
2 629 633 60
2 855 863 17
4 693 699
2 841 848 16
4 99 497
2 591 593 11
4 475 475
3 662 665 9880886915713059518
2 759 767 7
3 138 500 17769308332561790789
2 377 385 1
1 63...

output:

17107392241503669933
12334116376362625112
0
6456951739835200564
9971073695561689148
2802027920063294567
1036164630077188382
17606737366739661456
3673719133547364878
14283911652166609210
10307419488382662895
7570930610113533112
4760136262978142135
2686644875969537451
16340864373011062989
166150323341...

result:

ok 238 tokens

Test #10:

score: 0
Accepted
time: 4ms
memory: 19192kb

input:

1000 1000
1 72 236 30
1 50 509 27
1 13 108 25
2 886 894 4
3 655 875 4803545865429381065
3 383 783 11671115136637467033
1 585 927 23
2 504 509 1
1 30 147 26
2 741 749 16
4 270 679
4 173 186
2 144 145 23
3 221 230 3690281936266615260
3 239 771 8308954142750294924
3 563 791 15967473094317050982
2 223 2...

output:

7741491917409221922
0
1184088091910697156
9402573550842177896
16347258322020142583
10075791157671528329
15790910225201268145
3569527660563963307
15857736879027467782
12504414326160398443
10919437795207910592
16960732844939675104
17997032562817801024
8392051279069707625
5000292839030073720
1114739402...

result:

ok 235 tokens

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 583ms
memory: 103352kb

input:

300000 300000
1 237576 237663 1
3 16150 16208 9270412155482010138
2 175648 175692 1
4 190836 190849
4 199010 199097
1 73976 298801 1
3 89902 89939 6418828085116455990
3 55415 55461 12238963685511262676
3 119825 119875 8146944792877919309
3 135103 135158 218634681842812119
3 127261 127352 13291431184...

output:

0
0
0
0
0
0
12272376591028786218
0
0
0
0
0
0
0
0
0
0
0
0
0
0
954290611784159519
0
3778617232493240005
8956067326602310519
16588979141746646599
16938285947326957203
0
0
14783754218831034862
7601682967357904165
0
0
0
0
0
14319613256867159658
11584905325916393312
0
12745257730826081322
4657169178464751...

result:

wrong answer 26th words differ - expected: '7373452729428553855', found: '16588979141746646599'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #31:

score: 0
Wrong Answer
time: 65ms
memory: 10276kb

input:

300000 300000
1 85444 86076 59
1 41150 41411 71
1 278698 279414 45
1 238445 239202 56
1 29965 29984 49
1 282953 283272 37
1 34668 35653 86
2 198587 198744 28
1 270855 271611 58
1 2130 2965 773
1 161601 162298 937
1 50299 50435 36
1 100759 101198 64
1 120208 120543 84
1 295293 295732 34
1 112185 1129...

output:


result:

wrong answer Unexpected EOF in the participants output

Subtask #5:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #41:

score: 0
Wrong Answer
time: 5ms
memory: 3420kb

input:

40000 40000
4 576 27541
4 6386 23009
1 20941 21376 751
3 823 32062 5063552653037376179
2 13664 17318 2188
1 8143 18546 1303
1 96 22011 1709
2 20800 37184 3499
3 4098 33457 11559569033571630334
1 6686 15115 2973
3 11874 14936 5095502711361186497
4 423 21401
2 465 17984 1744
4 7029 8301
2 11477 13949 ...

output:


result:

wrong answer Unexpected EOF in the participants output

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%