QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#121241#3270. 魔塔 OLzhouhuanyi20 1976ms20240kbC++113.1kb2023-07-07 19:56:022023-07-07 19:56:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 19:56:06]
  • 评测
  • 测评结果:20
  • 用时:1976ms
  • 内存:20240kb
  • [2023-07-07 19:56:02]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 150000
#define M 50000
#define K 20
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],dp2[1<<K],ans[N+1];
node operator + (node x,node y)
{
    return (node){x.a+y.a,max(x.b+y.a,y.b)};
}
const int Base=30,Base2=15;
int q,length,lw[1<<K],lws[1<<K],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,pst;
    for (int i=0;i<(1<<Base2);++i)
	for (int j=1;j<=Base2;++j)
	    if (i&(1<<(j-1)))
	    {
		lw[i]=j,lws[i]=1<<(j-1);
		break;
	    }
    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=1;j<(1<<min(d,Base2));++j) pst=i+lw[j]-1,dp[j]=(node){st[pst].a,st[pst].b}+dp[j-lws[j]];
	if (i+Base2<=length)
	{
	    for (int j=1;j<(1<<(d-Base2));++j) pst=i+Base2+lw[j]-1,dp2[j]=(node){st[pst].a,st[pst].b}+dp2[j-lws[j]];
	}
	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&((1<<Base2)-1)]+dp2[res>>Base2];
	}
    }
    for (int i=1;i<=q;++i)
	if (c[i]=='?')
	    printf("%lld\n",max(ans[i].a,ans[i].b));
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 1ms
memory: 11800kb

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: 0ms
memory: 11756kb

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: 11804kb

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: 11804kb

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: 2ms
memory: 11724kb

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: 2ms
memory: 13824kb

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: 11972kb

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: 1ms
memory: 13784kb

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: 16120kb

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: 1ms
memory: 13816kb

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: 1ms
memory: 13816kb

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: 13836kb

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: 57ms
memory: 16964kb

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: 48ms
memory: 16840kb

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: 52ms
memory: 18180kb

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: 48ms
memory: 13080kb

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: 51ms
memory: 18184kb

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: 56ms
memory: 12924kb

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: 56ms
memory: 15144kb

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: 51ms
memory: 16720kb

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: 55ms
memory: 14980kb

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: 55ms
memory: 14936kb

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: 55ms
memory: 14832kb

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: 10
Accepted

Test #24:

score: 10
Accepted
time: 1961ms
memory: 20208kb

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:

640173034
640173034
1288949945
640173034
1383251963
648776911
936263387
6225405294
1584881750
1100294298
6171086456
5704673070
4575914076
3155191047
8023603142
2527253525
7167405476
0
10195623880
0
1402795465
4984468602
11654616273
1473610256
2027968013
4367888241
2304906071
2304906071
12018094056
2...

result:

ok 50000 lines

Test #25:

score: 0
Accepted
time: 1962ms
memory: 18156kb

input:

150000
+ 1787 8939 1 339346728 0
+ 3158 5092 1 855389002 0
+ 7832 1673 1 721154315 0
+ 1707 6586 1 559360588 0
? 6285 2437 1
+ 1490 7002 1 739345914 0
? 2815 2609 1
+ 8527 8829 1 367297793 0
+ 923 6751 1 126310301 0
+ 2810 6129 1 875334002 0
+ 7149 9872 1 658890299 0
+ 3495 467 1 349126714 0
+ 356 2...

output:

0
0
2915271787
4145341563
989601756
0
989601756
989601756
8854347677
7055669482
5291303583
3870297099
1187229746
7148740547
466075431
2404621423
7775443142
7682961442
2305192137
349126714
3903312117
14509564923
0
9584525312
5959691046
16191460507
6321152285
15631009768
4090015118
8330922702
14987834...

result:

ok 50000 lines

Test #26:

score: 0
Accepted
time: 1976ms
memory: 18172kb

input:

150000
? 9819 7010 1
+ 1517 9319 1 761082020 0
? 6420 6850 1
+ 9950 5950 1 915549489 0
+ 7039 2434 1 92974186 0
+ 2913 7849 1 984734480 0
+ 4517 8118 1 250711080 0
+ 7909 3583 1 184025459 0
+ 9524 1430 1 864047763 0
? 7547 9033 1
? 5504 5205 1
? 8491 3037 1
? 1043 3152 1
+ 9676 3886 1 426915433 0
+ ...

output:

0
0
1328419746
0
92974186
0
0
1323840030
199448068
0
0
0
1787413459
2330784601
2943820662
964261394
2925703990
1905971976
0
18077736464
7978811233
964261394
18814278526
18098823816
5066562470
8962935888
2311793337
1347531943
1347531943
2919782139
0
0
10193662595
10789276500
2542720149
3455776134
120...

result:

ok 50000 lines

Test #27:

score: 0
Accepted
time: 1942ms
memory: 18204kb

input:

150000
+ 930 118 1 979534399 0
? 484 60 1
? 365 143 1
? 19 252 1
+ 775 105 1 354040505 0
? 426 541 1
? 781 435 1
+ 314 306 1 4398445 0
+ 499 855 1 429484536 0
? 440 138 1
+ 855 955 1 687386644 0
+ 10 197 1 910103250 0
+ 217 375 1 770690507 0
? 401 111 1
+ 787 484 1 914331856 0
+ 907 872 1 789691385 ...

output:

0
0
0
0
354040505
0
0
354040505
1560780741
1952278514
3995739827
1084865603
4343100163
3107365561
2631450423
2627051978
1842473665
1084865603
1842473665
12282151973
0
7739054592
8715250511
5807771088
7236124275
0
0
8006814782
568585700
3086025393
2517439693
0
7314249953
2517439693
6965559181
7012239...

result:

ok 50000 lines

Test #28:

score: 0
Accepted
time: 1930ms
memory: 18264kb

input:

150000
+ 50 37 1 708972468 0
+ 18 62 1 186412810 0
? 42 92 1
+ 70 63 1 499167214 0
+ 87 37 1 9753881 0
+ 25 10 1 962187904 0
? 89 74 1
+ 93 17 1 414130698 0
+ 97 87 1 103340756 0
+ 79 5 1 737466371 0
+ 70 98 1 383081284 0
+ 30 18 1 950133777 0
+ 78 23 1 430459053 0
? 44 52 1
+ 27 70 1 866104461 0
+ ...

output:

186412810
2366494277
1912321681
1699654275
962187904
3494377803
962187904
3143862341
8986387511
0
737466371
3080247105
0
7624657274
214083964
4024194299
2437128825
5998424714
10777980738
10308326178
6943671240
1341655112
1746138247
3046563132
6436272368
13163376501
214083964
5840292537
1000922619
52...

result:

ok 50000 lines

Test #29:

score: 0
Accepted
time: 1922ms
memory: 20240kb

input:

150000
? 7 7 1
+ 4 1 1 684861229 0
? 8 4 1
+ 8 4 1 394234759 0
? 10 7 1
+ 8 10 1 174933586 0
+ 1 8 1 155093080 0
+ 3 5 1 360569664 0
+ 8 1 1 302476341 0
? 5 4 1
+ 3 1 1 309477964 0
+ 6 5 1 3345418 0
+ 1 9 1 31128204 0
+ 7 10 1 261898040 0
+ 6 10 1 20868263 0
+ 4 1 1 413664169 0
+ 3 8 1 660018338 0
+...

output:

0
684861229
1079095988
684861229
502073680
0
1945242559
502073680
309477964
0
0
4584156270
4770082565
7294103543
9629605008
12410412318
16531903872
10808215457
15636388917
2380411498
7702220303
10940353825
11254320459
10890764062
20674654718
4460547161
7598640300
25980420587
25606338059
1636053588
3...

result:

ok 50000 lines

Test #30:

score: 0
Accepted
time: 967ms
memory: 17596kb

input:

101000
+ 7599 908 1 339097838 0
+ 9787 306 1 529271711 0
+ 9497 9109 1 443251017 0
+ 4989 876 1 24346088 0
+ 4439 9648 1 148703162 0
+ 7017 3441 1 29320835 0
+ 8321 6853 1 38406269 0
+ 9000 5957 1 984032881 0
+ 3620 1790 1 508398856 0
+ 4241 1114 1 520652107 0
+ 3556 2810 1 139359541 0
+ 4977 5312 1...

output:

23021982437685
22545059244882
23042129573297
21846100962529
22945110330098
19797328975012
21954507061152
21938547433991
22563458945136
20996830751833
23267340294755
20455062519262
23747613178081
23034064177395
22238967148336
22302781110355
21052961261668
21399336171815
20963685974118
21331296071720
...

result:

ok 50000 lines

Test #31:

score: 0
Accepted
time: 968ms
memory: 17364kb

input:

101000
+ 789 45 1 699137225 0
+ 211 614 1 216996178 0
+ 936 887 1 769728088 0
+ 1 885 1 754680436 0
+ 807 370 1 107909447 0
+ 933 647 1 771120156 0
+ 951 125 1 663155095 0
+ 687 80 1 961858378 0
+ 619 811 1 212401348 0
+ 47 188 1 732924936 0
+ 433 313 1 425771280 0
+ 419 498 1 460805597 0
+ 656 82 1...

output:

22763116566605
22727118596689
1591695865691
21303547820084
5550039547345
389950008909
22074581887268
23212143702543
4999840967043
1672096249923
20481489222160
15916643229052
3937601889029
23254622393816
23162947580053
15329779967830
610975319558
1342327883395
2744701041558
22823414441394
15823998423...

result:

ok 50000 lines

Test #32:

score: 0
Accepted
time: 929ms
memory: 17584kb

input:

101000
+ 73 209 1 294643139 0
+ 32 676 1 844379704 0
+ 47 596 1 813038513 0
+ 38 591 1 655291231 0
+ 96 87 1 12424155 0
+ 81 878 1 53465899 0
+ 90 734 1 70086059 0
+ 88 455 1 550152926 0
+ 54 635 1 80304863 0
+ 45 919 1 964270228 0
+ 90 167 1 94063864 0
+ 9 821 1 323550583 0
+ 20 807 1 628078018 0
+...

output:

22735219955968
23425178960718
23452653687277
24175861017894
23571331067920
23646072416844
24448189134474
22526523982253
22905049545463
23199641100781
23002118400713
22044398366803
23594136940301
772761192740
22232199443974
23452715541655
5378617805460
24175922872272
23494858400419
22711677381556
227...

result:

ok 50000 lines

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:

100%
Accepted

Dependency #4:

0%