QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#114771 | #5022. 【模板】线段树 | lgvc# | 25 | 1239ms | 168144kb | C++23 | 2.1kb | 2023-06-23 15:55:13 | 2024-05-31 14:10:47 |
Judging History
answer
//这回只花了114514min就打完了。
//真好。记得多手造几组。
#include <bits/stdc++.h>
//#define int long long
#define pai 3.141592653589793238462643383279502884197169399375105820
#define MOD 1000000007
#define eps 0.00000001
inline int min(int a,int b) {return a<b?a:b;}
inline int max(int a,int b) {return a>b?a:b;}
#define ULL unsigned long long
#define LL long long
#define INF 0x3f3f3f3f
#define INF_LL 0x3f3f3f3f3f3f3f3f
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
*pp++=ch;
}
inline void pcc(){
fwrite(buf2,1,pp-buf2,stdout);
pp=buf2;
}
inline int read(void) {
register int x(0);register char c(getchar());
while(c<'0'||c>'9') {c=getchar();}
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
void write(int x) {
static int sta[20];
int top=0;
do {
sta[top++]=x%10,x/=10;
} while(x);
while(top) pc(sta[--top]+48);
}
void we(int x) {
write(x);
pc('\n');
}
inline bool cmp_xi(int a,int b) {return a<b;}
inline bool cmp_da(int a,int b) {return a>b;}
int T,N,Q,ct,st[250009],a[250009];
std::unordered_map<LL,int> vi;
int f(int x,int y) {
if(x==0) return a[y];
int m=vi[1ll*x*N+y];
if(m) return m-1;
int as=f(x-(1<<st[x]),y);
if(y>(1<<st[x])) as^=f(x-(1<<st[x]),y-(1<<st[x]));
vi[1ll*x*N+y]=as+1;
return as;
}
signed main(void) {
// freopen("m.in","r",stdin);
// freopen("m.out","w",stdout);
T=read();N=read();Q=read();
assert(T==4||T==5||T==6);
for(int i=1;i<=Q;i++) {
for(int j=19;j>=0;j--) {
if((i>>j)&1) {
st[i]=j;
break;
}
}
}
for(int i=1;i<=N;i++) {
a[i]=read();
}
while(Q--) {
int op=read();
if(op==1) {
int l=read(),r=read();
ct++;
} else {
int x=read();
we(f(ct,x));
}
}
for(int i=0;i<=19;i++) {
if((ct>>i)&1) {
for(int j=N;j>(1<<i);j--) {
a[j]^=a[j-(1<<i)];
}
}
}
for(int i=1;i<=N;i++) we(a[i]);
pcc();
return 0;
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
1 6 6 1 1 5 1 9 4 2 5 1 2 5 2 4 1 3 6 2 6 1 1 6
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #6:
score: 0
Runtime Error
input:
2 249998 99999 1048488450 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #10:
score: 0
Runtime Error
input:
3 250000 99999 1 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 0 1 1 0 1 0 0 1 1...
output:
result:
Subtask #4:
score: 13
Accepted
Test #14:
score: 13
Accepted
time: 743ms
memory: 97476kb
input:
4 249996 99997 309331355 195839266 912372930 57974187 363345291 954954162 650621300 389049294 821214285 263720748 231045308 844370953 768579771 664766522 681320982 124177317 32442094 297873605 743179832 1073656106 443742270 235746807 1054294813 974443618 422427461 307448375 1018255356 20105813 36821...
output:
611117059 866091251 300188933 0 478915924 1053588351 453142424 897441996 60971719 748656483 600408393 0 303761852 983037069 883016404 332332552 1069626159 860304528 851235295 561276840 389049294 681320982 484263000 351914192 620106464 667080579 733146026 375466744 0 347632358 737240082 321494160 0 3...
result:
ok 299980 numbers
Test #15:
score: 0
Accepted
time: 307ms
memory: 58384kb
input:
4 249996 99997 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 707358968 0 0 0 165359261 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 301087804 0 0 0 0 ...
result:
ok 348991 numbers
Test #16:
score: 0
Accepted
time: 33ms
memory: 16188kb
input:
4 249996 100000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0 0 0 0 0 0 0 0 412012733 460047966 0 0 0 94984489 0 0 0 0 1010860949 0 0 0 336953687 0 0 0 0 0 655564155 25780913 662736870 0 0 0 0 0 679917886 0 998313118 0 0 0 0 0 171168202 20014081 336953687 0 0 0 0 1018313742 0 997397452 0 849015355 0 16108473 0 0 0 504340154 0 397006673 0 0 0 0 0 0 290851883 ...
result:
ok 250950 numbers
Test #17:
score: 0
Accepted
time: 849ms
memory: 107500kb
input:
4 249999 99998 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 956381802 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1021925694 922314342 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 300062 numbers
Subtask #5:
score: 12
Accepted
Test #18:
score: 12
Accepted
time: 13ms
memory: 7436kb
input:
5 249997 99997 860563869 428592873 58576739 761578583 47999879 294581118 988847649 569566599 640106250 440172702 178219106 966598261 763325707 846927552 877923116 145156535 246778542 25949847 507939778 116507169 555239769 259969305 328955819 171606729 535970481 121608060 4437163 370976515 713807003 ...
output:
860563869 717285236 452329866 773393204 485721677 965902221 831024341 890990738 455498944 92913689 556500009 102303365 264515518 445496274 654612933 988537886 165104807 364103659 952755344 576499197 775866335 1003839403 606880290 1006459039 1005979559 588810854 592470517 765610807 123827263 86327854...
result:
ok 249997 numbers
Test #19:
score: 0
Accepted
time: 13ms
memory: 7152kb
input:
5 249998 100000 1055401468 532211763 131695513 214363867 831955115 452049333 729606869 69161863 428100767 90941242 729034740 90774107 332674212 930394013 601735907 104187221 1017052616 31513597 868964816 1054507185 926990168 75998133 1039482150 781325037 680316641 471310435 780674964 330142918 10271...
output:
1055401468 532211763 131695513 214363867 831955115 452049333 729606869 69161863 428100767 90941242 729034740 90774107 332674212 930394013 601735907 104187221 1017052616 31513597 868964816 1054507185 926990168 75998133 1039482150 781325037 680316641 471310435 780674964 330142918 1027184688 750941669 ...
result:
ok 249998 numbers
Test #20:
score: 0
Accepted
time: 14ms
memory: 7424kb
input:
5 249999 65535 206222027 1038492265 248834236 84032585 981309757 273118313 589015947 1002433231 482381717 342803573 48417408 196676553 50772773 199061806 637191822 974252922 289297532 48985206 415073252 593023329 9193325 632026989 55397875 918843456 476033799 664362612 383124333 926156312 133237149 ...
output:
206222027 833392802 1064859678 981091415 515434 272673027 861602440 149219399 337930194 4891559 44591399 152134382 169335243 30058725 607153771 505513233 253743469 234136859 357115647 907147166 916304115 322324382 276499053 650082861 987810090 494507870 196056115 1016828459 996842422 602075803 53081...
result:
ok 249999 numbers
Subtask #6:
score: 0
Time Limit Exceeded
Dependency #5:
100%
Accepted
Test #21:
score: 16
Accepted
time: 942ms
memory: 111544kb
input:
6 249999 99998 234899190 294042590 622374272 592723113 719234312 350081074 842293736 684699037 330659123 145765638 707972395 212219898 665588169 1002656251 377046330 569400576 515159132 246671859 367313733 436193585 1056439739 889727758 441186237 802117710 672761337 1013893805 760105556 959623512 10...
output:
416342969 682608684 897388094 564167584 723521403 277032360 571217154 804968920 345689708 20430886 2669323 397914023 682539746 743678615 902811241 79705781 117866215 29290630 463835109 948618157 996425135 333840809 879030503 756069154 651860206 62844241 563208222 473841643 306068071 945671265 755499...
result:
ok 340922 numbers
Test #22:
score: 0
Accepted
time: 186ms
memory: 46012kb
input:
6 249999 100000 440794180 373448998 924631752 1029747555 1025197824 772227211 39885098 362601933 28836613 109487897 1065155159 170512808 1054469991 504110707 412993411 172546234 861597564 320825471 551313957 607675657 108258007 713412450 183442416 266654936 968422736 230720896 824830683 653610670 10...
output:
98475211 195528780 696822840 514087003 829956911 329558613 774154603 206369270 459595700 862203687 923064620 893978487 446169540 162819606 623685563 362210402 266466497 536712664 619196444 636251427 621982108 29822991 825999568 1023819390 976493671 1002043855 522408337 819431256 487829199 839724281 ...
result:
ok 258991 numbers
Test #23:
score: 0
Accepted
time: 1239ms
memory: 168144kb
input:
6 249997 99996 858874420 647336645 792849435 487078011 572740439 880018128 888095353 792485726 562377029 925278515 769802546 863097170 1024187886 86325040 278572503 296068408 305389187 156383560 564344122 985485618 352643959 100128572 51313514 939087520 196935800 175799309 561623994 704660004 265677...
output:
432854594 738728738 262426424 538231132 618966731 444275244 553066863 973600567 229016163 137911233 474170208 151027732 489894673 52703384 860246793 29393762 677235209 677602352 528898618 55456646 169243833 468519972 485795189 732890985 359625381 702665297 407151543 225249034 52286602 259376944 8254...
result:
ok 316451 numbers
Test #24:
score: -16
Time Limit Exceeded
input:
6 249996 99998 397969543 991721013 639702540 604481296 351426688 333740122 724850461 729736402 79245133 118976945 532880690 120525599 614643743 490724539 699303708 215416342 87908710 952073016 139568877 646769946 252759252 177392171 163619316 265404108 1038973785 470689235 333983939 483290379 506253...
output:
result:
Subtask #7:
score: 0
Runtime Error
Dependency #5:
100%
Accepted
Test #28:
score: 0
Runtime Error
input:
7 249999 99998 1028875149 290751586 85260062 527433830 11253389 381520904 163374626 882045937 328797576 362761070 107207247 721987314 848366187 492948114 913994419 980121735 553555299 238308272 517289115 493658637 535863518 18389830 59694996 328276770 970756488 409396240 782649706 568544673 92874299...
output:
result:
Subtask #8:
score: 0
Skipped
Dependency #1:
0%