QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#87736 | #5302. Useful Algorithm | zsj6315 | RE | 3851ms | 187060kb | C++14 | 2.5kb | 2023-03-14 07:05:46 | 2023-03-14 07:05:50 |
Judging History
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...