QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#87736#5302. Useful Algorithmzsj6315RE 3851ms187060kbC++142.5kb2023-03-14 07:05:462023-03-14 07:05:50

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-14 07:05:50]
  • 评测
  • 测评结果:RE
  • 用时:3851ms
  • 内存:187060kb
  • [2023-03-14 07:05:46]
  • 提交

answer

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define mod 998244353
#define N 100005
#define M 17
#define inf 0x3f3f3f3f
int n,m,Q,w[M],c[N],d[N];
ll lastans;

//DS
multiset<int> A[M][1<<M];
struct SGT1{
	struct SGT{
		int ans,mxa,mxb;
	}t[1<<(M+1)];
	int Max(int a,int b){
		return a<b?b:a;
	}
	void pushup(int nd){
		t[nd].mxa=Max(t[nd<<1].mxa,t[nd<<1|1].mxa);
		t[nd].mxb=Max(t[nd<<1].mxb,t[nd<<1|1].mxb);
		t[nd].ans=Max(Max(t[nd<<1].ans,t[nd<<1|1].ans),t[nd<<1].mxb+t[nd<<1|1].mxa);
	}
	void build(int nd,int l,int r){
		if(l==r){
			t[nd].mxa=t[nd].mxb=t[nd].ans=-inf;
			return;
		}
		else{
			int mid=(l+r)>>1;
			build(nd<<1,l,mid);
			build(nd<<1|1,mid+1,r);
		}
	}
	void updatea(int nd,int l,int r,int x,int aa){
		if(l==r){
			t[nd].mxa=aa;
			return;
		}
		else{
			int mid=(l+r)>>1;
			if(x<=mid)updatea(nd<<1,l,mid,x,aa);
			else  updatea(nd<<1|1,mid+1,r,x,aa);
			pushup(nd);
		}
	}
	void updateb(int nd,int l,int r,int x,int bb){
		if(l==r){
			t[nd].mxb=bb;
			return;
		}
		else{
			int mid=(l+r)>>1;
			if(x<=mid)updateb(nd<<1,l,mid,x,bb);
			else  updateb(nd<<1|1,mid+1,r,x,bb);
			pushup(nd);
		}
	}
	int findmx(){
		return t[1].ans;
	}
}T[M];

void add(int k,int a,int b,int op){
	if(op==1)A[k][a].insert(b);
	else A[k][a].erase(A[k][a].find(b));
	if(A[k][a].size()){
		T[k].updatea(1,1,(1<<k),a+1,*A[k][a].rbegin());
		T[k].updateb(1,1,(1<<k),(1<<k)-a,*A[k][a].rbegin());
	}
	else{
		T[k].updatea(1,1,(1<<k),a+1,-inf);
		T[k].updateb(1,1,(1<<k),(1<<k)-a,-inf);
	}
}
void ins(int a,int b,int op){
	fr(i,1,m){
		int ag=a&((1<<i)-1);
		add(i,ag,b,op);
	}
}
ll Query(){
	ll res=0;
	fr(i,1,m)res=max(res,1ll*T[i].findmx()*w[i]);
	return res;
}

int readi(){
	int s=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')s=s*10+c-'0',c=getchar();
	return s;
}
ll readl(){
	ll s=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')s=s*10+c-'0',c=getchar();
	return s;
}
int main(){
	n=readi(),m=readi(),Q=readi();
	fr(i,1,m)T[i].build(1,1,(1<<i));
	fr(i,1,m)w[i]=readi();
	fr(i,1,n)c[i]=readi();
	fr(i,1,n)d[i]=readi();
	fr(i,1,n)ins(c[i],d[i],1);
	printf("%lld\n",lastans=Query());
	while(Q--){
		ll x=readl()^lastans,u=readl()^lastans,v=readl()^lastans;
		ins(c[x],d[x],-1);
		ins(c[x]=u,d[x]=v,1);
		printf("%lld\n",lastans=Query());
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 35ms
memory: 108196kb

input:

5 3 3
1 2 4
0 0 1 2 7
10 10 5 3 1
27 24 29
20 16 19
13 8 9

output:

24
16
8
0

result:

ok 4 number(s): "24 16 8 0"

Test #2:

score: 0
Accepted
time: 32ms
memory: 108036kb

input:

10 3 10
927067928 939794644 439925712
4 7 6 2 4 2 0 7 0 7
207761141 796144622 434713413 101162902 804840394 950218456 666995722 154361380 192946720 522277478
1786020431157499334 1786020431157499335 1786020431397722754
1496424903210009138 1496424903210009136 1496424902707960940
981667153012455665 981...

output:

1786020431157499328
1496424903210009136
981667153012455664
981667153012455664
817082674424719944
1083086338546577104
1186096888772143904
1186096888772143904
1186096888772143904
768437095486384888
848350340146561056

result:

ok 11 numbers

Test #3:

score: 0
Accepted
time: 32ms
memory: 108012kb

input:

100 5 100
90634477 839424973 368714032 715789796 976912516
14 25 23 26 21 6 18 25 13 16 1 11 6 19 23 30 20 16 9 5 15 14 18 25 20 21 16 20 1 17 5 20 29 21 23 30 14 21 16 25 0 10 30 15 5 18 20 15 16 14 8 13 25 3 19 1 28 25 20 4 25 31 13 22 21 5 4 27 24 0 3 25 14 9 25 27 6 31 23 17 22 0 20 14 20 20 10 ...

output:

1948430837606303184
1925731571920031664
1925731571920031664
1918610389626725016
1918610389626725016
1912989537852540976
1912989537852540976
1943875008041762216
1880564337285514332
1872790752298860048
1872790752298860048
1872790752298860048
1860886514497440896
1840781733071162176
1840781733071162176
...

result:

ok 101 numbers

Test #4:

score: 0
Accepted
time: 27ms
memory: 108216kb

input:

200 10 200
686225366 625898088 889833199 755030970 349397678 32982490 273727441 273558302 259659090 988780410
764 308 833 222 75 641 80 22 298 315 295 545 284 459 960 884 566 848 491 631 930 542 972 519 28 570 603 1013 120 480 482 900 538 1022 131 1007 380 694 176 737 172 480 945 763 459 389 34 593 ...

output:

1976367332381717700
1976367332381717700
1976367332381717700
1919420428070056950
1896682288410976680
1851396613326110610
1848014565081016770
1848014565081016770
1844553517236285570
1844515090263211740
1839357062871524190
1835762131192937760
1831576340926210500
1820368528821786240
1813214370325218480
...

result:

ok 201 numbers

Test #5:

score: 0
Accepted
time: 24ms
memory: 108564kb

input:

1000 10 1000
634018763 100170818 567660357 254302610 840960097 802296108 283969325 368515437 441547602 397000462
612 405 890 783 513 253 461 140 625 8 464 401 1011 271 27 355 794 222 734 246 846 310 88 374 330 844 353 706 415 584 993 492 816 456 342 954 436 90 339 808 56 517 1019 996 922 705 138 209...

output:

1681866301913143852
1681866301913143852
1680999430153635088
1676312717485049238
1674196766011546180
1673931937585479716
1673454371483675162
1672867243418513254
1672867243418513254
1672867243418513254
1672669252819036156
1671478710655473838
1671478710655473838
1665328148837561252
1665328148837561252
...

result:

ok 1001 numbers

Test #6:

score: 0
Accepted
time: 3851ms
memory: 187060kb

input:

100000 16 100000
427137788 524903900 786287591 199228679 318168922 101722889 789810886 488566259 846829249 575667147 767258103 63802528 801156446 519047646 781774765 555029219
4621 48336 12816 52645 55523 30344 27584 3940 41894 60346 15947 30387 19024 31860 33462 13493 28048 58004 12794 7590 22857 6...

output:

1693617423394106504
1693589359472794644
1693492085043791263
1693480115112356648
1693470840638421600
1693453134285654259
1693444900564866232
1693444900564866232
1693416918785991525
1693393685178715961
1693387980090065448
1693380527992674248
1693380527992674248
1693380527992674248
1693380527992674248
...

result:

ok 100001 numbers

Test #7:

score: 0
Accepted
time: 30ms
memory: 108204kb

input:

10 3 10
6 10 28
2 1 6 4 1 6 4 5 6 6
6 9 11 3 11 10 7 20 9 12
1128 1122 1128
675 673 681
674 679 695
1282 1289 1283
1290 1295 1309
1178 1180 1182
566 560 561
510 507 488
693 698 695
754 752 753

output:

1120
672
672
1288
1288
1176
560
504
700
756
616

result:

ok 11 numbers

Test #8:

score: 0
Accepted
time: 31ms
memory: 108020kb

input:

100 5 100
3 12 29 85 248
19 16 18 16 1 2 2 13 21 2 12 28 5 16 4 25 10 11 25 21 10 1 26 25 26 16 6 16 17 10 26 1 17 5 7 16 5 16 2 0 21 9 16 20 4 10 16 14 21 18 17 3 12 10 16 25 16 22 8 12 26 8 8 18 16 25 21 25 11 8 28 22 28 2 18 20 3 20 2 14 4 9 11 26 25 13 21 8 2 14 28 25 26 1 13 9 7 5 17 18
60 2 21...

output:

29760
29016
31248
31248
31248
31248
29016
28272
27776
27776
27032
27032
27032
27032
27528
27528
26784
28520
28272
26536
28024
28024
28024
28024
26536
25792
25792
25792
27528
27528
27528
27032
25792
25792
27032
25792
25544
25544
26288
25296
25296
25048
25048
25048
24800
23808
23808
23312
26288
26288
...

result:

ok 101 numbers

Test #9:

score: -100
Runtime Error

input:

200 10 200
4 13 32 82 247 734 2192 6565 19688 59054
0 0 130 320 40 10 2 80 33 384 128 32 160 768 32 2 144 34 80 640 528 96 768 272 0 6 384 3 36 256 96 514 65 320 258 192 24 514 128 132 256 2 132 512 128 10 6 65 513 128 80 129 66 5 384 3 136 72 65 2 768 272 257 10 10 512 65 48 512 4 24 128 4 48 1 384...

output:


result: