QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121212 | #3270. 魔塔 OL | zhouhuanyi | 10 | 66ms | 9736kb | C++11 | 2.8kb | 2023-07-07 19:28:33 | 2023-07-07 19:28:36 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 150000
#define M 10000
#define K 10
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int sgn(int x)
{
if (x>0) return 1;
else if (x==0) return 0;
else return -1;
}
struct reads
{
int x,y,z,a,b,num,snum,snum2;
bool operator < (const reads &t)const
{
if (sgn(a)!=sgn(t.a)) return sgn(a)>sgn(t.a);
else if (sgn(a)==1) return a-b>t.a-t.b;
else return b>t.b;
}
};
reads st[N+1];
bool cmp(reads a,reads b)
{
return a.x<b.x;
}
bool cmp2(reads a,reads b)
{
return a.y<b.y;
}
bool cmp3(reads a,reads b)
{
return a.z<b.z;
}
bool cmp4(reads a,reads b)
{
return a.num<b.num;
}
struct node
{
long long a,b;
};
node dp[1<<K],ans[N+1];
node operator + (node x,node y)
{
return (node){x.a+y.a,max(x.b+y.a,y.b)};
}
int Base=10,q,length,A[M+1],B[M+1],C[M+1],ps[N+1],X[N+1],Y[N+1],Z[N+1];
char c[N+1];
int main()
{
int d,rst,res;
q=read();
for (int i=1;i<=q;++i)
{
cin>>c[i];
if (c[i]=='+') ++length,st[length]=(reads){read(),read(),read(),read(),read(),0,i},swap(st[length].a,st[length].b),st[length].a=st[length].b-st[length].a;
else if (c[i]=='-') st[read()].snum2=i;
else X[i]=read(),Y[i]=read(),Z[i]=read();
}
sort(st+1,st+length+1);
for (int i=1;i<=length;++i) st[i].num=i,ps[st[i].snum]=ps[st[i].snum2]=i;
sort(st+1,st+length+1,cmp);
for (int i=1;i<=q;++i) X[i]=lower_bound(st+1,st+length+1,(reads){X[i]+1,0,0},cmp)-st-1;
for (int i=1;i<=length;++i) st[i].x=i;
sort(st+1,st+length+1,cmp2);
for (int i=1;i<=q;++i) Y[i]=lower_bound(st+1,st+length+1,(reads){0,Y[i]+1,0},cmp2)-st-1;
for (int i=1;i<=length;++i) st[i].y=i;
sort(st+1,st+length+1,cmp3);
for (int i=1;i<=q;++i) Z[i]=lower_bound(st+1,st+length+1,(reads){0,0,Z[i]+1},cmp3)-st-1;
for (int i=1;i<=length;++i) st[i].z=i;
sort(st+1,st+length+1,cmp4);
for (int i=1;i<=length;i+=Base)
{
d=min(i+Base-1,length)-i+1;
for (int j=0;j<(1<<d);++j)
{
dp[j]=(node){0,0};
for (int k=1;k<=d;++k)
if (j&(1<<(k-1)))
dp[j]=dp[j]+(node){st[i+k-1].a,st[i+k-1].b};
}
rst=0;
for (int j=1;j<=M;++j) A[j]=B[j]=C[j]=0;
for (int j=i;j<=min(i+Base-1,length);++j) A[st[j].x]|=(1<<(j-i)),B[st[j].y]|=(1<<(j-i)),C[st[j].z]|=(1<<(j-i));
for (int j=2;j<=M;++j) A[j]|=A[j-1],B[j]|=B[j-1],C[j]|=C[j-1];
for (int j=1;j<=q;++j)
{
if (c[j]!='?'&&i<=ps[j]&&ps[j]<=min(i+Base-1,length)) rst^=(1<<(ps[j]-i));
else res=A[X[j]]&B[Y[j]]&C[Z[j]]&rst,ans[j]=ans[j]+dp[res];
}
}
for (int i=1;i<=q;++i)
if (c[i]=='?')
printf("%lld\n",max(ans[i].a,ans[i].b));
return 0;
}
详细
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 2ms
memory: 7580kb
input:
10 + 2 1 1 3 4 + 1 2 2 2 5 ? 2 2 2 + 1 1 1 8 2 ? 2 2 1 ? 1 2 2 - 1 ? 2 2 2 - 3 ? 1 2 2
output:
2 7 5 5 2
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 9692kb
input:
24 + 1753 1095 4823 848018166 5601858 + 3635 2923 7293 78801729 4982097 + 4314 6396 5125 589512425 8363663 ? 8152 8403 6056 + 9016 7943 8050 764333567 3409718 ? 3516 8598 7385 ? 1126 7574 1443 + 2684 1515 2348 83534456 3012204 - 5 ? 1861 8978 2163 - 4 ? 480 2246 9251 - 1 + 3844 6148 4596 110822346 7...
output:
1429166928 848018166 0 0 0 0 0 0
result:
ok 8 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 7624kb
input:
24 + 9833 6751 5339 125176046 14445 + 1422 2896 2855 729112474 32204 + 636 3368 6257 631353523 97285 + 7661 7136 8410 801391911 74940 ? 7519 1330 3067 ? 9524 4467 711 ? 2291 8608 9213 - 1 ? 1174 1586 7861 ? 2265 4657 349 ? 8213 4439 7824 + 9135 101 6409 977821442 34327 + 1115 2298 9752 392083250 697...
output:
0 0 1360368712 0 0 1360368712 729112474 729112474
result:
ok 8 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 7680kb
input:
24 + 5489 9970 1398 56343180 451 + 1396 1562 433 123478310 271 - 2 + 7608 4501 7224 982256325 947 - 3 ? 9813 5754 2918 ? 2389 7502 4690 + 5393 498 3406 73387341 297 ? 621 6378 5221 ? 3593 3767 6323 - 1 + 3286 7926 6941 820762494 364 - 5 + 8217 6480 9506 484820290 71 - 6 + 9300 262 4419 859278667 105...
output:
0 0 0 0 0 0 0 0
result:
ok 8 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 5620kb
input:
8 ? 1117 6081 8661 ? 5702 6655 5962 ? 4712 8281 9732 ? 4472 3953 2253 ? 8402 8576 2723 ? 8258 6776 1630 ? 9363 4534 9896 ? 8271 8778 1846
output:
0 0 0 0 0 0 0 0
result:
ok 8 lines
Test #6:
score: 0
Accepted
time: 1ms
memory: 9692kb
input:
24 + 310 6758 7068 581664379 614379561 ? 431 4963 9146 + 8040 7145 2374 921183974 119186212 ? 739 2475 4540 + 7023 2014 2972 87001226 131388922 + 332 1474 3058 965714110 106555937 - 1 ? 6232 3770 731 ? 3571 5680 4059 + 6128 4706 1280 517406107 709876522 ? 7499 5319 7619 ? 8343 4010 2781 + 2990 2854 ...
output:
0 0 0 965714110 728855999 0 191994852 191994852
result:
ok 8 lines
Test #7:
score: 0
Accepted
time: 2ms
memory: 7628kb
input:
24 ? 7531 9176 7945 + 6869 6976 9568 811496150 65260266 + 6002 7147 3653 399332739 802592034 + 1589 1206 9875 491845336 674971274 + 2606 7949 8709 732507238 685138894 - 4 - 3 + 7773 2691 4846 806580794 444791436 ? 8302 1260 612 + 9474 585 6602 228111503 673775897 + 7377 2531 1730 989204815 313215502...
output:
0 0 0 0 0 0 0 0
result:
ok 8 lines
Test #8:
score: 0
Accepted
time: 2ms
memory: 7676kb
input:
24 + 6076 6882 697 357720969 18505713 + 8522 7101 7498 273203817 247602668 + 5282 5228 6668 389453604 672327934 ? 6379 8137 1715 ? 7691 1160 2306 + 2065 3609 2107 39462790 995011849 - 2 + 7821 3053 4992 54012550 598488583 ? 2742 7408 4111 + 8142 2626 2703 378261715 799364458 + 8988 6063 8298 8459843...
output:
357720969 0 39462790 0 0 0 0 0
result:
ok 8 lines
Test #9:
score: 0
Accepted
time: 1ms
memory: 9736kb
input:
24 + 4703 1944 1160 450781972 720568789 + 3502 6991 8127 106832475 971539963 ? 3141 943 3234 + 5361 8172 8148 172500308 209720541 - 3 - 1 + 4124 2386 6673 396124268 408795532 + 7267 8100 7795 710193258 706757641 ? 3147 654 9372 + 7795 2301 1587 223112271 672239899 ? 4553 738 5182 + 6188 7219 243 764...
output:
0 0 0 0 0 0 0 0
result:
ok 8 lines
Test #10:
score: 0
Accepted
time: 2ms
memory: 7844kb
input:
24 + 1015 3099 4819 69198894 934987604 + 1971 6075 3089 18416465 126949453 + 3346 4984 4780 756144 637251010 + 9173 1405 1768 90360802 606947317 + 1452 1393 6947 86736593 700812438 + 7794 9412 1997 52466993 263586896 - 5 + 6442 6634 8262 33830753 203825632 ? 5518 522 7828 - 1 - 3 + 3365 8793 7708 64...
output:
0 0 0 0 0 0 0 0
result:
ok 8 lines
Test #11:
score: 0
Accepted
time: 2ms
memory: 7628kb
input:
24 + 9703 133 3965 55149 848473280 ? 794 7392 2211 ? 6854 1133 7922 + 5774 6768 6550 19909 92266756 - 2 ? 4784 2895 2924 + 2589 9679 8865 93993 586178413 + 6266 516 8968 99691 77932883 ? 5982 5547 905 + 7947 3208 3227 44903 268728227 - 5 - 4 + 6508 3419 6547 26144 770044013 ? 3120 2629 5910 + 8616 2...
output:
0 0 0 0 0 0 0 0
result:
ok 8 lines
Test #12:
score: 0
Accepted
time: 0ms
memory: 7576kb
input:
24 + 3428 3207 272 398860932 94104753 ? 7644 5501 6242 ? 4375 4880 3925 ? 1803 4173 8176 ? 6042 1710 2170 + 3748 5518 3602 909430193 42284174 + 3649 9013 9199 375710242 7718045 - 3 ? 919 5751 4803 + 3223 324 8116 531239473 10475148 ? 1915 3129 9903 + 7144 6800 8556 652921806 11521155 - 1 - 4 + 4427 ...
output:
398860932 398860932 0 0 0 0 432397460 0
result:
ok 8 lines
Subtask #2:
score: 7
Accepted
Dependency #1:
100%
Accepted
Test #13:
score: 7
Accepted
time: 55ms
memory: 7940kb
input:
15000 + 9754 4951 2299 36950620 330476254 ? 7852 3754 6437 + 7960 5847 3889 877365182 511620385 + 2042 1318 3674 509235230 295832114 + 8026 1900 3586 787277573 238947685 ? 3297 71 4102 ? 7652 9321 3721 ? 1782 8456 2128 ? 3892 8535 3934 + 4911 3952 9686 951709847 5471156 + 567 5092 9346 132609563 645...
output:
0 0 509235230 0 509235230 0 0 799337462 0 0 0 575363546 0 955299529 799337462 0 0 1724967630 320029391 590850186 1250598046 0 548236941 509235230 548236941 389915580 509235230 0 578425355 799337462 1197972240 0 0 35119488 837528941 758929477 891443369 548236941 0 1242763152 0 35119488 0 0 0 0 351194...
result:
ok 5000 lines
Test #14:
score: 0
Accepted
time: 62ms
memory: 7844kb
input:
15000 + 9000 6045 9181 863134447 327523157 + 5800 3917 4897 494849846 170888604 + 8224 524 7309 567221629 163056241 ? 2839 4181 2426 ? 1731 3056 6432 + 8778 8718 3130 146110843 137080516 + 4985 3689 8556 456546147 7602401 + 356 9954 3979 273061519 454609666 + 1209 9046 4448 642768233 777950592 + 879...
output:
0 0 0 144925021 0 0 846135812 0 0 0 1426212455 1659355410 827991846 846135812 1194975799 0 846135812 377185177 0 248809656 2138119062 438946756 0 438946756 2724060363 748592853 0 873547760 846135812 0 383144069 227838083 39166976 39166976 39166976 846135812 39166976 39166976 39166976 3947224442 3916...
result:
ok 5000 lines
Test #15:
score: 0
Accepted
time: 66ms
memory: 8168kb
input:
15000 + 951 7138 255 320722052 324570060 + 2596 7803 3430 410802879 748644857 ? 3555 6250 6021 ? 3881 2359 5828 ? 2110 933 7043 + 4862 2175 1664 481128464 24445604 ? 1280 3044 69 + 368 299 6465 110630763 605821477 + 1298 1572 1823 6340608 435831189 + 8497 471 8990 862173030 294426772 ? 2582 3988 118...
output:
0 0 0 0 0 6340608 6340608 184769081 0 6340608 6340608 110630763 6340608 6340608 0 184769081 0 110630763 144559506 6340608 0 0 184769081 0 6340608 6340608 6340608 284186499 209374819 6340608 6340608 166088998 600045165 0 24708843 6340608 6340608 6340608 110630763 600045165 6340608 0 6340608 6340608 6...
result:
ok 5000 lines
Test #16:
score: 0
Accepted
time: 62ms
memory: 7876kb
input:
15000 ? 1330 3972 8167 + 7771 2045 28 71596349 316831431 + 4392 5643 8439 793300118 365317022 ? 1145 1085 1131 ? 1981 4834 3010 ? 7898 2215 2137 + 9452 8525 6012 308068582 222805994 + 3109 1021 3834 149338880 460129515 + 8252 8596 2476 25387218 893568152 + 9457 8518 1637 365077612 577489093 + 7750 4...
output:
0 0 0 71596349 0 149338880 0 0 71596349 149338880 482509483 0 149338880 0 339204739 0 0 149338880 646121546 0 339204739 0 347036011 0 0 840777389 0 818079693 25387218 0 8400682 0 28267956 586256202 940165346 0 8400682 5137674 940165346 0 0 1146605530 623425462 1009743383 8400682 0 0 0 8400682 635897...
result:
ok 5000 lines
Test #17:
score: 0
Accepted
time: 66ms
memory: 7796kb
input:
15000 ? 8212 7747 6199 ? 5369 4852 6221 + 857 4971 2870 21781664 537676236 ? 9139 6445 3549 ? 8576 2601 6708 + 4132 7656 9581 659855253 194286236 ? 3171 5622 517 ? 3171 327 2791 + 5787 5851 4846 918160613 261675926 + 1379 2503 9812 686149995 413030048 + 320 3121 1973 208594175 204418683 + 9169 5837 ...
output:
0 0 21781664 0 0 0 0 0 417771032 0 933665604 208594175 249449409 21781664 21781664 417771032 0 0 986604907 29341218 21781664 29341218 173452390 173452390 29341218 0 310828376 302388712 310828376 0 0 698493757 173452390 7884628 0 85153293 21781664 0 0 643737804 0 10510955 7884628 21781664 1387723437 ...
result:
ok 5000 lines
Test #18:
score: 0
Accepted
time: 62ms
memory: 7908kb
input:
15000 + 837 3441 1582 5253755 930660276 ? 8689 9131 528 + 4211 2422 5160 6252539 907522408 ? 5609 9790 4958 + 3432 9848 2969 4896645 940041091 + 3206 796 2996 4324022 502262890 + 5174 3152 4568 113382 730527877 + 980 3333 9883 3057033 196077695 + 4799 5142 3509 3458598 100286630 + 9905 3615 8329 927...
output:
0 5253755 3458598 5253755 5253755 5253755 9436006 4324022 113382 113382 4324022 4324022 0 0 867679 0 0 782618 867679 867679 0 0 5253755 0 867679 0 782618 0 0 867679 113382 113382 0 867679 0 867679 0 0 867679 782618 0 0 0 0 0 867679 867679 113382 782618 0 700552 535909 0 535909 535909 1670398 535909 ...
result:
ok 5000 lines
Test #19:
score: 0
Accepted
time: 65ms
memory: 7904kb
input:
15000 ? 3626 6634 706 ? 582 4658 8319 + 8038 8232 6351 148817232 19413256 + 3461 40 3308 437404415 36165359 + 4151 5967 4070 30914737 15176710 ? 1288 5080 6184 + 4930 9177 4330 947817077 4805014 ? 5408 4013 1507 + 1577 348 6484 542555954 13288929 + 5453 364 6644 751430050 669281 ? 5356 1904 8389 + 7...
output:
0 0 0 0 943795010 1681936131 270965968 1382835375 0 3579152160 2639972120 632435278 3039344651 270965968 0 270965968 437404415 0 270965968 0 9127712031 2340849315 7463345443 0 1359397476 0 1377000336 0 3316860695 437404415 9298965753 380650058 1538402434 380650058 417208885 4307614967 400461565 0 0 ...
result:
ok 5000 lines
Test #20:
score: 0
Accepted
time: 65ms
memory: 7920kb
input:
15000 ? 3611 820 322 + 68 6093 7344 309660603 8512708 + 9882 7331 2103 909793528 3687386 + 1138 4890 983 723391503 1141995 + 4152 9237 9559 368251712 1852709 + 1125 9752 5938 889181325 3511910 + 3283 9654 5264 798148638 5602588 + 3969 5422 5395 231270203 718652 + 844 9893 7504 648724319 7248904 + 64...
output:
0 0 0 723391503 723391503 1842658494 3508915764 90640885 2547470891 0 234293253 2126743406 0 1886611066 1362525704 90640885 0 0 234293253 6846238386 0 5602549623 2436552350 1238971762 2141877364 920903399 4563307221 0 0 0 723391503 0 10337046004 652693183 0 2094945541 723391503 19414268394 652693183...
result:
ok 5000 lines
Test #21:
score: 0
Accepted
time: 66ms
memory: 7940kb
input:
15000 + 2801 8433 1829 827936405 969585 ? 3554 6367 5498 + 2376 6776 7720 574207248 923476 + 6613 3146 9378 418383056 692192 ? 5159 1876 4183 ? 8151 2128 7976 + 5623 5911 6955 870974472 262457 + 7705 3889 1572 267612426 193840 + 5878 8297 1889 949419857 909460 ? 2892 6894 9481 + 9002 6208 2127 17602...
output:
0 0 0 574207248 1447046366 220786949 220786949 198485575 0 0 220786949 0 4729943861 1058959264 6235959933 0 4713794925 0 0 2808741354 8162816820 14909424 0 615261353 497270752 1066222454 6951160136 2520242767 937344669 101280125 2250020267 0 11483417654 1946958292 517978806 14909424 14909424 3799993...
result:
ok 5000 lines
Test #22:
score: 0
Accepted
time: 61ms
memory: 7748kb
input:
15000 ? 1822 8820 1908 ? 6083 1623 4227 + 2418 2824 8807 17003027 76795 + 8008 4258 9437 554693365 68917 ? 2489 3921 7965 + 3031 2477 9191 233409376 44619 + 275 7141 8883 632058327 24232 ? 2823 344 8326 ? 4155 616 839 + 4987 8144 4847 428926401 72189 + 1182 1452 4110 318600919 38488 ? 7018 1554 9239...
output:
0 0 0 0 0 318600919 318600919 318600919 318600919 822156885 1752483691 301111585 0 301111585 830297218 301111585 830297218 2204007159 0 318600919 338944729 422177019 810476550 948847527 0 0 0 931541984 2883343968 2060522423 5573300097 2636499601 810476550 318600919 3775501120 0 5139311198 2342378136...
result:
ok 5000 lines
Test #23:
score: 0
Accepted
time: 65ms
memory: 7876kb
input:
15000 ? 4398 952 1402 + 6182 1283 9449 125619308 3324 + 5052 3754 4403 940063798 7205 ? 5829 8922 1931 ? 3773 9074 6359 + 5199 3920 7495 700019470 6744 + 5061 4344 6013 240536850 6853 + 822 2757 5213 726945179 9781 + 2472 2802 3895 668906250 3499 + 7575 213 5230 996820178 794 ? 2508 2979 6516 + 7428...
output:
0 0 0 1395841648 0 1395841648 0 0 5247832105 249492314 6975588404 9526409743 1269626113 0 0 0 3312824127 0 0 1388900157 1130300143 0 6478380651 0 675045491 0 0 971474622 0 15013028304 7606104219 724850564 1858905499 49811071 249492314 2109763404 21604570710 3196438136 2036028508 1595679425 231376802...
result:
ok 5000 lines
Subtask #3:
score: 0
Time Limit Exceeded
Test #24:
score: 0
Time Limit Exceeded
input:
150000 + 588 392 1 640173034 0 ? 7190 2026 1 ? 8338 9467 1 + 332 5522 1 648776911 0 ? 650 9239 1 ? 6609 1361 1 + 6028 8919 1 315490561 0 + 6129 3818 1 716541323 0 + 2679 2249 1 94302018 0 ? 4777 8851 1 + 1382 186 1 295931805 0 + 3956 7752 1 275694182 0 + 6412 2498 1 363908456 0 + 8317 3132 1 2800724...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #33:
score: 0
Time Limit Exceeded
input:
150000 ? 5 2 1 + 4 2 1 783649445 157723097 + 3 4 1 281409092 43289613 + 2 3 2 673972686 123253436 ? 3 5 3 ? 4 2 3 + 5 5 2 534941804 768558960 + 2 4 4 103433782 913423755 + 1 2 3 99618767 608469807 + 5 4 4 852574365 108454346 ? 4 5 5 + 1 2 4 647253960 383418735 + 1 5 1 854207792 811999048 + 4 2 4 995...
output:
result:
Subtask #5:
score: 0
Time Limit Exceeded
Test #47:
score: 0
Time Limit Exceeded
input:
150000 + 9842 1 1 26088315 73696334 + 2239 1 1 340356927 653719371 + 349 1 1 632186088 849099938 ? 908 1 1 + 5153 1 1 487261860 697113681 ? 984 1 1 + 5694 1 1 800262114 571078829 ? 1152 1 1 + 3322 1 1 855670925 826813576 + 8218 1 1 45843349 617723019 + 3988 1 1 641119549 840483348 + 3253 1 1 1654789...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%