QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#318636#5449. 楼梯catagory10 112ms7768kbC++233.1kb2024-01-31 16:26:482024-01-31 16:26:48

Judging History

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

  • [2024-01-31 16:26:48]
  • 评测
  • 测评结果:10
  • 用时:112ms
  • 内存:7768kb
  • [2024-01-31 16:26:48]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define SZ(x) ((LL)(x.size()))
using namespace std;
long long read(){
  long long q=0,w=1;
  char ch=getchar();
  while(ch>'9' || ch<'0'){if(ch=='-')w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){q=q*10+(ch-'0');ch=getchar();}
  return q*w;
}
void write(LL x){
  if(x<0){putchar('-');x=(-x);}
  if(x>9)write(x/10);
  putchar('0'+x%10);
}
void writeln(LL x){write(x);puts("");}
void writecs(LL x){write(x);putchar(' ');}

const long long lim = 1000000000;
namespace seg{
  const long long SIZE = 20000000+95;
  struct node{LL l,r,d,t;}s[SIZE];LL tot;
  void pushup(LL p){s[p].d=max(s[s[p].l].d,s[s[p].r].d)+s[p].t;return ;}
  void update(LL &p,LL x,LL y,LL v,LL l=1,LL r=lim){//将 [x,y] 区间内的部分加 v
    if(y<l || r<x || x>y)return ;
    s[++tot]=s[p];p=tot;
    if(x<=l&&r<=y){s[p].d+=v;s[p].t+=v;return ;}
    LL mid=(l+r)>>1;
    if(x<=mid)update(s[p].l,x,y,v,l,mid);
    if(mid<y)update(s[p].r,x,y,v,mid+1,r);
    pushup(p);return ;
  }
  void make(LL &p,LL l=1,LL r=lim,LL tag=0){//将小于 0 的部分设置为 0
    s[++tot]=s[p];p=tot;
    if(s[p].d+tag<=0){s[p].l=s[p].r=0;s[p].d=s[p].t=-tag;return ;}
    if(l==r)return ;
    tag+=s[p].t;LL mid=(l+r)>>1;
    if(s[s[p].r].d+tag>=0)make(s[p].r,mid+1,r,tag);
    else {make(s[p].l,l,mid,tag);make(s[p].r,mid+1,r,tag);}
    pushup(p);return ;
  }
  LL query(LL p,LL x,LL l=1,LL r=lim){//得到其中一行的值
    if(!p)return 0;
    if(l==r)return s[p].t;
    LL mid=(l+r)>>1;
    if(x<=mid)return query(s[p].l,x,l,mid)+s[p].t;
    else return query(s[p].r,x,mid+1,r)+s[p].t;
  }
  LL get(LL p,LL y,LL l=1,LL r=lim,LL tag=0){//得到其中一列的值
    if(l==r)return ((s[p].d+tag>=y)?(l):(l-1));
    tag+=s[p].t;LL mid=(l+r)>>1;
    if(s[s[p].r].d+tag>=y)return get(s[p].r,y,mid+1,r,tag);
    else return get(s[p].l,y,l,mid,tag);
  }
}

const long long N = 300000+95;
long long T,rt,__rt[N];
LL GET(LL x,LL y){
  LL X=(seg::get(rt,y)-x+1);
  LL Y=(seg::query(rt,x)-y+1);
  if(X<=0||Y<=0)return -1;
  return (X+Y-1);
}
int main(){
  T=read();
  for(LL t=1;t<=T;t++){
    char opt;cin>>opt;
    if(opt=='+'){
      LL a=read(),b=read();
      seg::update(rt,1,a,b);
    }
    else if(opt=='-'){
      LL a=read(),b=read();
      seg::update(rt,a,lim,-b);seg::make(rt);
      
    }
    else if(opt=='R'){
      LL u=read();
      rt=__rt[(t-1)-u];
    }
    else if(opt=='?'){
      LL q=read();
      LL Y=seg::query(rt,1),X=seg::get(rt,1);
      assert((X!=0)==(Y!=0));
      if(!X){puts("-1 -1");continue;}
      /*      cout<<"> X = "<<X<<" Y = "<<Y<<endl;
      for(LL i=1;i<=X;i++){
	for(LL j=1;j<=Y;j++)cout<<GET(i,j)<<" ";
	cout<<endl;
	}*/
      LL fl=0;
      for(LL i=1;i<=X&&!fl;i++){
	LL l=1,r=Y,ans=-1;
	while(l<=r){
	  LL mid=(l+r)>>1;
	  //	  cout<<" mid = "<<mid<<" i = "<<i<<" GET(i,mid) = "<<GET(i,mid)<<endl;
	  if(GET(i,mid)>=q){l=mid+1;ans=mid;}
	  else {r=mid-1;}
	}
	//	cout<<" ans = "<<ans<<" GET(i,ans) = "<<GET(i,ans)<<endl<<endl;
	if(ans!=-1&&GET(i,ans)==q){writecs(i);writeln(ans);fl=1;break;}
      }
      assert(fl);
    }
    __rt[t]=rt;
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 5772kb

input:

1000
- 1 999995
? 770771330
? 688406105220012703
? 466054413
? 1466199
? 940610359316496655
? 310504014100463831
? 765557590
? 419614901
? 830584303
? 85199513
? 768715778674812284
? 742663363105169125
? 859012516258231128
? 168409807482711289
? 842755243
? 618667253264707663
? 957265852
+ 1 1
+ 1 1...

output:

-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 1
1 3
1 1
1 1
1 3
1 1
1 3
1 1
1 1
1 1
1 3
1 3
1 3
1 3
1 1
1 1
1 1
1 1
1 3
1 3
1 3
1 3
1 2
1 1
1 2
1 1
1 2
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 2
1 1
1 ...

result:

ok ok

Test #2:

score: 0
Accepted
time: 2ms
memory: 7760kb

input:

1000
- 1 999999992
? 426873616
- 1 256
? 670399288694575053
? 270955652351585633
? 258266169
? 358158412890035660
- 1 579
? 882074593944476252
? 575229109486341356
? 343017523563388060
? 73907450
? 730903768
? 413587891090231085
? 803451715032296303
? 945196920
+ 1 783
? 783
? 29
? 87
+ 1 933
+ 1 62...

output:

-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 1
1 755
1 697
1 2343
1 2925
1 1
1 2941
1 2769
1 2925
1 1
1 1
1 2941
1 2510
1 2522
1 2497
1 2329
1 2426
1 1
1 2521
1 2497
1 1262
1 2522
1 1262
1 2426
1 1
1 2329
1 1
1 1
1 1
1 2510
1 2522
1 2522
1 2497
1 2522
1 1262
1 2497...

result:

ok ok

Test #3:

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

input:

1000
? 724684671
- 229 22497
+ 29 60
+ 275 51
+ 2 60
+ 50 60
+ 750 8
+ 856 8
+ 513 36
+ 65 59
+ 565 35
+ 36 60
? 1292
+ 17 60
+ 697 8
? 8
+ 416 38
? 1398
+ 205 51
+ 40 60
? 503
+ 57 60
+ 6 60
+ 393 39
? 2
+ 54 60
+ 100 56
+ 803 8
? 32
? 112
+ 130 56
+ 488 36
+ 30 60
+ 20 60
? 1
+ 63 59
? 1
+ 25 60
+...

output:

-1 -1
1 1
1 499
1 1
18 219
1 813
1 907
1 831
2 1149
2 1208
2 1377
1 2057
1 1
2 2177
1 1
1 1363
2 2469
1 1
1 2495
1 1
2 2924
1 3261
1 3322
1 3320
1 4049
1 1
1 4079
1 4147
1 1
1 3832
1 4446
1 5696
1 6374
1 5212
1 6172
1 6052
1 5692
1 1
1 6112
2 6292
1 6292
1 4012
1 5932
1 5812
1 6383
1 2813
1 4612
1 6...

result:

ok ok

Test #4:

score: 0
Accepted
time: 8ms
memory: 7760kb

input:

1000
? 612443313965411255
- 398 867638065
- 338 149214194
? 412057943687439209
+ 29 2
+ 288 7
+ 1 60
+ 4 60
+ 181 12
? 1
+ 84 38
+ 234 8
? 237
+ 39 51
+ 2 60
+ 132 2
? 1
+ 7 2
+ 9 59
+ 61 2
+ 19 56
+ 3 60
+ 14 2
+ 342 7
+ 397 6
+ 5 60
+ 7 57
+ 288 1
+ 14 54
+ 132 11
? 29
+ 29 49
? 1122
? 102
+ 61 37...

output:

-1 -1
-1 -1
1 141
1 34
1 300
1 649
1 1
1 626
235 14
1 745
1 1
1 763
1 1
235 14
1 1
1 1
1 1
1 1
1 1
235 14
235 14
235 14
235 14
1 1
1 1
235 14
235 14
235 14
1 1
235 14
1 763
1 1
235 14
1 763
235 14
1 1
1 566
1 565
1 541
1 1
3 583
1 1
1 763
3 583
3 583
1 745
3 583
3 583
1 1
1 1
1 1
3 583
1 554
1 611
1...

result:

ok ok

Test #5:

score: 0
Accepted
time: 59ms
memory: 5776kb

input:

1000
? 603050749
+ 78 59
+ 909 2
? 3
+ 66 60
+ 335 51
+ 245 51
+ 618 36
? 3
+ 38 60
+ 47 60
+ 827 34
+ 25 60
+ 345 51
+ 497 37
+ 30 60
+ 76 59
+ 6 60
+ 92 59
+ 285 51
+ 4 60
+ 29 60
+ 40 60
? 3
+ 53 60
+ 88 59
+ 14 60
+ 1 60
+ 42 60
+ 521 37
? 3
+ 74 59
+ 52 60
+ 32 60
? 1
+ 22 60
+ 5 60
+ 23 60
+ 1...

output:

-1 -1
76 61
64 259
2 1030
1 1364
1 1545
1 1841
1 1901
1 1849
1 2140
1 692
1 2195
1 1
1 2164
1 2433
1 2313
1 2653
1 1
1 3216
1 3246
1 1
1 1
1 3879
1 1
1 4229
1 1
1 4327
1 1
1 4473
1 1
1 5000
1 1
1 5218
1 5611
1 5612
1 5292
1 5026
1 6623
1 1
1 6743
1 1
1 7253
1 7383
37 5595
1 1
25 5595
37 5595
1 1
27 ...

result:

ok ok

Test #6:

score: 0
Accepted
time: 16ms
memory: 7768kb

input:

1000
+ 639 6
+ 6 60
? 44
? 1
+ 25 58
+ 201 35
+ 419 6
? 1
+ 76 2
+ 474 6
+ 10 60
+ 863 5
+ 14 60
+ 18 60
+ 227 35
+ 112 49
+ 8 60
? 11
? 1
? 1364
+ 12 60
+ 751 5
? 1429
+ 4 60
? 1
? 1489
+ 807 5
? 1
+ 11 60
+ 31 58
? 1
+ 149 2
+ 64 55
+ 34 58
? 1727
? 157
+ 919 5
? 4
+ 16 60
+ 46 55
+ 28 58
+ 58 55
...

output:

1 28
6 66
6 165
1 497
6 502
1 1
1 1
4 627
1 1
4 632
4 750
1 1
1 716
1 870
1 698
1 531
1 937
1 1
1 1477
1 1435
1 1483
1 1
1 1439
1 1610
1 1615
1 1935
1 1
15 1415
1 1
18 1114
19 1114
1 1
1 708
16 1114
1 2254
7 1114
16 1114
1 2229
19 1114
18 1114
1 2253
16 1114
1 708
19 1114
19 1114
1 1
1 2203
18 1114
...

result:

ok ok

Test #7:

score: 0
Accepted
time: 36ms
memory: 5716kb

input:

1000
- 886 3325373
- 421 609251347
- 74 509944584
- 353 790375490
- 597 946044374
- 542 516826393
+ 14 60
+ 15 60
+ 19 60
+ 46 59
? 2
+ 23 60
+ 56 59
+ 167 51
+ 60 59
+ 197 51
+ 77 56
? 1
+ 187 51
+ 542 13
+ 17 60
+ 357 39
+ 39 60
? 103
? 1339
+ 269 40
+ 147 51
? 2
? 1430
? 1
+ 21 60
+ 20 60
+ 82 56...

output:

13 239
14 575
1 710
1 1
13 889
1 1
14 889
13 1065
14 1065
12 1190
1 629
10 1244
1 1448
1 1532
1 1739
1 1794
1 1854
1 1
1 1831
1 2088
1 1
1 2489
1 1
1 1
1 2927
1 3180
1 1
1 3329
1 4289
1 1
1 1885
1 1
358 115
1 4584
1 4693
1 3591
1 1
1 4863
59 1877
32 1877
51 1877
1 4572
1 4206
1 1
687 1
270 1
881 1
1...

result:

ok ok

Test #8:

score: 0
Accepted
time: 44ms
memory: 7760kb

input:

1000
? 836688957840823224
- 306 679936336
+ 48 60
+ 58 59
+ 35 60
+ 28 60
+ 102 56
+ 520 36
+ 167 51
+ 23 60
? 31
+ 15 60
+ 50 2
? 341
+ 8 60
+ 66 59
+ 47 60
? 601
? 1202
+ 43 60
+ 347 37
+ 683 6
? 734
+ 87 56
+ 628 2
+ 26 60
+ 495 36
+ 21 60
+ 243 50
? 1732
+ 7 60
+ 9 60
+ 39 60
+ 10 60
+ 97 56
+ 3...

output:

-1 -1
1 434
1 211
1 148
1 1
1 154
1 1
1 1781
1 1951
1 2561
1 1
1 2734
1 2951
1 3349
1 4021
1 4116
1 1
1 4307
1 1
1 1
1 2882
1 4905
1 1
1 5074
1 3726
1 1
1 1
1 1
1 5295
1 1
37 1737
1 1
73 1737
11 1737
75 1737
69 1737
1 5340
75 1737
51 1737
69 1737
61 1737
1 5442
73 1737
37 1737
75 1737
75 1737
51 173...

result:

ok ok

Test #9:

score: 0
Accepted
time: 41ms
memory: 5712kb

input:

1000
+ 44 60
+ 24 60
? 163
+ 52 60
? 1
? 3
? 33
+ 28 60
+ 258 49
? 546
+ 54 60
? 6
+ 79 59
? 665
+ 306 49
+ 39 60
+ 32 60
+ 282 49
+ 270 49
? 70
+ 61 2
? 1
+ 6 60
+ 698 33
+ 615 34
+ 43 60
+ 50 60
? 1
+ 8 60
+ 59 60
+ 535 35
+ 156 55
+ 57 60
+ 83 59
+ 840 4
+ 135 56
? 2152
+ 110 56
+ 561 35
+ 318 49...

output:

1 1
24 180
22 180
1 171
1 1
19 349
1 1
1 629
24 677
6 924
1 1
1 1286
6 1670
6 1786
1 1
1 1
1 2024
1 2273
1 2360
1 2692
1 1
3 2262
1 3102
1 2802
1 1182
1 3218
1 3268
1 1
1 3596
1 3592
1 3577
1 3718
1 3719
1 1
1 1
1 4381
1 4729
1 1
1 1
1 4818
1 4896
1 1
1 4938
1 1
1 5054
1 2172
1 5280
1 3756
1 5462
1 ...

result:

ok ok

Test #10:

score: 0
Accepted
time: 5ms
memory: 7768kb

input:

1000
- 1 999999996
? 503511061
? 999085692614634733
? 647103043
? 820196349493776381
? 652137897
+ 1 102
? 1
? 102
- 1 997
+ 1 348
? 87
? 12
? 4
+ 1 426
+ 1 313
? 1087
- 1 285
? 802
? 1
+ 1 131
? 933
? 1
? 311
+ 1 279
+ 1 531
? 3
? 1743
? 249
? 1
? 83
? 7
? 249
? 1
? 21
? 581
? 3
? 83
+ 1 846
? 863
...

output:

-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 102
1 1
1 262
1 337
1 345
1 1
1 1
1 802
1 1
1 933
1 623
1 1741
1 1
1 1495
1 1743
1 1661
1 1737
1 1495
1 1743
1 1723
1 1163
1 1741
1 1661
1 1727
1 1
1 2589
1 2587
1 2587
1 1
1 1727
1 2589
1 2589
1 1899
1 1
1 1891
1 1
1 1256
1 1408
1 1414
1 2086
1 2085
1 2080
1 1044
1 1...

result:

ok ok

Test #11:

score: 0
Accepted
time: 16ms
memory: 5716kb

input:

1000
? 58814603
+ 532 3
+ 60 2
? 134
+ 265 5
? 1
+ 1 30
+ 10 30
+ 476 4
+ 395 5
+ 11 30
? 1
+ 12 30
+ 40 26
+ 9 30
+ 23 29
? 755
+ 317 5
+ 4 30
? 10
+ 343 5
+ 422 4
+ 91 20
+ 17 2
? 1
+ 6 30
+ 25 29
+ 504 3
? 883
+ 15 30
+ 50 26
+ 114 2
+ 291 5
+ 8 30
? 1
+ 14 30
+ 2 30
+ 239 6
+ 139 6
+ 70 21
+ 449...

output:

-1 -1
399 3
60 10
1 109
1 1
1 250
1 290
1 1
1 445
1 603
4 419
1 1
1 788
1 844
1 402
1 820
1 849
28 7
318 7
450 7
370 7
81 7
1 1
165 7
423 7
396 7
1 950
1 1
266 7
1 957
1 956
1 844
266 39
1 956
140 39
1 1
16 39
240 39
190 39
1 889
1 908
1 253
18 389
20 389
8 389
16 389
14 389
1 1
18 389
1 253
1 956
1...

result:

ok ok

Test #12:

score: 0
Accepted
time: 19ms
memory: 5712kb

input:

1000
? 641775127
+ 658 6
? 663
+ 57 2
+ 27 30
+ 157 21
? 2
+ 22 30
+ 464 8
+ 14 30
? 56
+ 219 10
? 1
+ 48 29
? 1
? 823
+ 21 30
+ 147 21
+ 1 30
+ 18 30
? 1
+ 6 30
+ 97 26
+ 283 9
+ 20 30
+ 72 26
+ 87 26
+ 19 30
? 1111
+ 633 6
+ 7 30
? 31
+ 52 29
? 1
+ 127 21
+ 44 29
+ 50 29
+ 261 10
? 1
+ 28 30
+ 4 3...

output:

-1 -1
1 1
26 59
1 93
14 137
14 166
1 1
1 277
1 1
2 434
1 519
1 608
1 1
1 1
1 1
1 803
1 713
1 1
1 1008
1 1
1 1431
1 1434
1 1499
1 1556
1 1
1 1535
1 1628
1 1
1 1701
1 1
1 1731
1 1768
1 942
1 1
1 1819
1 942
1 1817
1 1
1 942
1 1
1 1817
1 1817
1 1
1 1819
1 1
1 1817
1 1819
1 1
1 942
1 1819
1 1817
1 1457
1...

result:

ok ok

Test #13:

score: 0
Accepted
time: 48ms
memory: 5792kb

input:

1000
? 322718911
? 527680755138194048
- 127 243926522
- 449 695974349
- 191 588919912
+ 30 30
? 59
+ 78 29
+ 856 5
+ 16 30
+ 25 30
+ 50 30
+ 52 30
+ 191 20
+ 60 29
+ 150 2
? 109
+ 135 26
+ 4 30
+ 44 30
+ 29 30
+ 6 30
? 1236
+ 397 6
+ 297 19
+ 14 30
+ 472 6
+ 908 5
+ 76 29
? 1
+ 33 30
+ 110 26
+ 622 ...

output:

-1 -1
-1 -1
1 1
1 156
1 1
4 476
1 467
4 587
1 1
4 649
1 394
4 704
1 542
1 263
1 888
1 1
1 1
1 1273
1 1398
1 964
1 1428
1 1
1 1
1 1492
1 1059
1 1
1 1572
1 1
1 1802
1 1866
1 1
1 1
1 2082
1 2094
1 1
1 2210
1 2216
1 2334
1 2440
1 2457
1 1
1 2576
1 964
398 56
548 56
598 56
1 1
310 56
1 236334
1 236311
1 ...

result:

ok ok

Test #14:

score: 0
Accepted
time: 20ms
memory: 5768kb

input:

1000
+ 24 30
+ 2 30
+ 93 28
+ 32 30
+ 96 28
+ 114 28
+ 69 2
+ 6 30
+ 55 30
? 349
? 1
? 1
+ 375 19
+ 836 6
? 1
+ 911 6
+ 11 30
+ 183 25
+ 159 25
+ 15 30
+ 60 30
+ 141 25
+ 231 2
+ 53 30
+ 105 28
+ 75 28
+ 611 6
+ 147 25
+ 25 30
? 1
+ 17 30
? 507
? 9
+ 4 30
? 1
+ 7 30
+ 636 6
+ 12 30
? 539
? 231
? 3
+...

output:

1 1
2 236
2 236
2 261
2 581
1 200
1 604
2 641
7 177
1 493
1 706
2 737
1 1
1 1
1 1
1 432
1 1546
1 1
1 1
1 1676
1 1
1 1778
1 1
1 2022
2 2055
3 1587
1 1967
1 2123
1 1
1 2511
1 1
1 1737
1 2661
1 1
1 2728
1 1
1 2877
1 1
1 1
1 1089
1 2693
1 3039
1 1770
1 1
1 1
1 3259
1 3249
1 1
38 2197
1 1
1 1
38 2197
38 ...

result:

ok ok

Test #15:

score: 0
Accepted
time: 37ms
memory: 7696kb

input:

1000
- 60 823078266
+ 306 20
+ 589 8
+ 74 29
+ 54 30
? 1
+ 72 29
+ 751 7
+ 20 30
+ 8 30
+ 134 26
+ 405 20
+ 895 7
? 565
+ 48 30
? 1160
? 10
+ 23 30
+ 119 26
+ 94 29
? 1245
+ 727 8
? 1253
+ 82 29
+ 19 30
+ 36 30
+ 44 30
+ 55 30
+ 799 7
+ 3 30
? 1
+ 124 26
? 1
? 1465
+ 428 2
+ 264 21
+ 41 30
+ 823 7
+...

output:

54 87
9 38
1 1
1 264
1 1
1 1
3 545
3 571
1 1
3 694
3 805
3 889
1 250
2 1162
1 1
1 1247
1 1339
1 1362
1 1
1 1387
1 1
1 1621
1 1218
1 1787
1 1306
1 1
1 1
1 1
1 2123
1 1729
1 1
1 2199
1 2229
1 2431
1 1
1 2527
1 1
1 2913
1 2973
1 2999
1 3073
1 3288
1 2311
1 3368
1 3476
1 3522
1 3541
1 3009
13 3249
1 1
7...

result:

ok ok

Test #16:

score: 0
Accepted
time: 13ms
memory: 5800kb

input:

1000
? 200865510
+ 509 4
+ 16 12
+ 256 5
? 23
+ 62 11
+ 3 12
+ 31 12
+ 29 12
+ 4 12
+ 200 5
? 593
? 1
+ 64 11
+ 392 4
+ 296 5
+ 124 9
+ 192 5
+ 446 4
+ 280 5
+ 78 11
+ 338 4
+ 51 12
+ 25 12
+ 383 4
+ 500 4
+ 41 12
+ 100 9
? 1
+ 47 12
+ 14 12
+ 374 4
+ 482 4
+ 12 12
+ 356 4
+ 128 9
+ 52 12
+ 80 11
+ ...

output:

-1 -1
1 14
1 1
3 85
3 196
1 1
1 1
1 1
1 1
1 328
1 500
1 416
1 515
1 1
3 574
2 596
4 154
1 1
1 1
3 530
1 759
1 1
1 809
1 857
1 870
1 869
1 1
1 885
1 904
1 903
1 921
1 1
1 589
1 1
1 1
1 1
1 1096
1 1129
1 1
1 384
48 600
33 600
46 600
1 1188
1 1
49 600
1 1126
1 1187
16 600
1 1185
49 600
42 600
49 600
1 ...

result:

ok ok

Test #17:

score: 0
Accepted
time: 15ms
memory: 5656kb

input:

1000
? 997038533866592106
+ 563 3
+ 158 8
+ 213 3
+ 11 12
+ 393 3
+ 623 3
? 654
+ 42 12
? 6
? 9
+ 423 3
? 1
+ 243 3
+ 40 12
? 57
+ 713 3
+ 38 12
? 1
? 263
? 789
+ 503 3
+ 19 12
+ 163 8
? 812
+ 4 12
? 412
+ 233 3
+ 57 12
+ 22 12
+ 673 3
+ 183 3
+ 41 12
+ 44 12
+ 313 3
? 442
+ 18 12
+ 373 3
? 31
+ 37 ...

output:

-1 -1
1 1
6 44
3 44
11 47
1 45
11 77
7 21
1 1
1 1
120 12
8 24
1 167
4 209
1 1
1 1
1 237
4 245
1 282
4 283
1 1
1 229
1 359
2 345
1 1
1 429
1 478
1 1
1 534
1 551
6 449
1 572
1 575
1 577
1 584
1 1
1 634
1 635
1 647
1 745
1 732
1 679
1 780
1 859
1 1
1 1
1 914
2 212
1 1
1 991
1 1017
1 1
1 1041
1 1047
1 1...

result:

ok ok

Test #18:

score: 0
Accepted
time: 49ms
memory: 5712kb

input:

1000
? 591451888148632183
- 478 549549332
- 787 581090850
- 265 537152516
+ 32 12
+ 427 5
+ 590 4
+ 58 12
? 1
+ 63 12
? 317
+ 395 5
+ 41 12
? 651
+ 139 9
? 60
+ 17 12
+ 97 11
+ 403 5
+ 23 12
+ 57 12
+ 19 12
? 362
+ 105 11
+ 51 12
+ 99 11
+ 387 5
+ 89 11
+ 680 4
? 28
+ 127 9
+ 85 11
? 888
+ 119 9
+ 1...

output:

-1 -1
32 33
111 9
1 1
1 52
67 14
1 178
1 1
1 1
17 250
1 1
17 262
9 299
1 344
1 1
1 1
9 526
3 530
6 585
1 1
1 578
1 1
6 628
1 1
7 126
1 531
6 675
1 616
1 536
2 709
1 1
3 714
3 714
1 1
1 740
3 742
2 771
1 1
1 793
1 807
1 817
1 1
2 880
3 899
3 928
1 832
1 828
1 633
2 271
3 1063
3 1120
1 768
1 1
1 365
1...

result:

ok ok

Test #19:

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

input:

1000
? 856936698
+ 836 3
? 419
+ 120 11
+ 776 3
? 1
+ 118 11
+ 98 11
? 1
+ 79 12
+ 63 12
? 898
+ 141 2
? 900
+ 876 3
? 1
+ 386 3
+ 376 3
? 949
+ 696 3
? 2
+ 31 12
+ 8 12
+ 108 11
+ 52 12
+ 146 8
? 1007
? 1
+ 456 3
? 505
+ 38 12
+ 176 8
+ 616 3
+ 75 12
+ 45 12
+ 216 8
+ 59 12
+ 51 12
+ 39 12
+ 606 3
...

output:

-1 -1
418 3
120 17
98 39
1 1
1 1
63 68
1 1
62 77
1 1
8 132
1 16
8 274
6 289
18 39
1 291
8 313
7 351
8 365
4 307
6 394
8 406
8 494
1 1
1 1
7 543
8 543
7 555
8 578
1 84
7 714
3 115
1 631
1 1
1 1
1 1
2 971
1 847
2 1008
2 1099
1 1
2 1148
2 1148
1 1109
2 1208
1 1229
1 1
1 1
2 1296
1 1342
1 1359
1 1
1 136...

result:

ok ok

Test #20:

score: 0
Accepted
time: 56ms
memory: 5716kb

input:

1000
- 928 780094783
- 710 398698340
- 355 708243512
- 222 934705837
- 273 29457417
+ 7 12
+ 166 8
+ 113 11
+ 139 11
+ 181 8
+ 35 12
+ 21 12
+ 801 3
? 877
+ 53 12
+ 127 11
+ 88 12
+ 301 3
? 183
? 1
+ 196 8
+ 441 3
+ 125 11
+ 47 12
+ 271 2
+ 151 11
? 962
+ 601 3
+ 38 12
+ 221 8
+ 45 12
? 997
+ 34 12
...

output:

1 1
1 45
7 115
1 1
1 1
7 209
1 1
1 1
7 221
1 1
7 239
1 1
6 338
1 1
1 351
1 1
1 1
1 369
7 381
1 1
20 26
7 396
2 359
1 1
1 1
1 260
4 499
4 514
1 1
1 1
4 570
1 583
1 1
5 235
4 710
1 774
1 1
1 652
4 793
1 832
1 712
1 584
1 925
2 932
1 954
1 1
3 958
1 1
1 972
1 197
1 966
1 852
2 1136
4 1163
1 1194
1 1193...

result:

ok ok

Test #21:

score: 0
Accepted
time: 73ms
memory: 5660kb

input:

1000
+ 8 12
+ 636 3
+ 15 12
+ 94 12
+ 356 3
+ 85 12
? 13
+ 556 3
+ 206 8
+ 24 12
+ 20 12
+ 111 11
? 49
? 7
+ 79 12
+ 846 3
+ 131 11
+ 77 12
+ 13 12
? 995
+ 546 3
+ 21 12
? 1010
+ 47 12
? 73
+ 27 12
+ 57 12
+ 816 3
+ 151 11
+ 211 8
+ 786 3
+ 54 12
+ 856 3
+ 886 3
+ 486 3
? 1132
+ 536 3
+ 12 12
? 1147...

output:

1 49
1 71
2 100
1 1
1 1
1 125
1 1
1 1
1 243
1 176
1 1
1 341
1 1
1 1
6 374
1 1
1 1
1 433
1 377
6 470
1 1
1 1
6 654
1 709
1 701
1 1
6 757
4 820
1 830
1 391
6 948
6 996
1 1
1 1119
1 1
1 1158
1 1
1 1181
1 1048
1 1
1 587
1 825
1 1
1 1
1 1026
1 1
1 1511
1 1499
1 1419
1 1576
1 1
1 1
1 1654
1 1266
1 1704
1 ...

result:

ok ok

Test #22:

score: 0
Accepted
time: 5ms
memory: 5712kb

input:

1000
+ 593 132415
- 310 420098
+ 576 965794
+ 509 638949
- 637 368901
+ 46 196629
+ 619 517472
+ 424 441788
+ 772 340443
+ 418 139594
- 21 147269
+ 383 456861
- 628 598537
+ 51 595087
+ 146 948842
- 942 435406
- 357 40209
+ 811 716421
+ 806 540386
+ 204 538624
- 891 312107
+ 598 65368
+ 355 739033
+...

output:

1 1
6 66847345
1 66844514
1 1
1 66823788
6 66847345
6 66847345
1 1
1 66844514
1 1
6 66847345
6 66847345
1 66844514
6 66847345
1 1
1 1
1 1
6 66847345
1 1
1 66844514
6 66847345
6 66847345
1 1
1 66844514
1 1
1 66823788
1 1
1 66844514
6 66847345
6 66847345
1 1
1 1
1 1
6 66847345
1 1
1 1
1 1
6 66847345
6...

result:

ok ok

Subtask #2:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #23:

score: 20
Accepted
time: 88ms
memory: 5660kb

input:

1000
- 1 999992
? 637280166636841974
? 122747834
+ 1 1
? 1
? 1
? 1
? 1
- 1 1
? 770322629409376789
+ 1 1
? 1
? 1
? 1
? 1
- 1 1
+ 1 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
? 1
+ 1 1
+ 1 1
? 3
+ 1 1
? 2
? 1
+ 1 1
? 5
+ 1 1
? 6
? 1
? 3
? 2
? 1
+ ...

output:

-1 -1
-1 -1
1 1
1 1
1 1
1 1
-1 -1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 3
1 4
1 1
1 1
1 6
1 4
1 5
1 6
1 1
1 7
1 5
1 8
1 1
1 7
1 10
1 9
1 1
1 10
1 9
1 1
1 6
1 9
1 10
1 1
1 1
1 9
1 10
1 9
1 1
1 6
1 10
1 1
1 9
1 7
1 10
...

result:

ok ok

Test #24:

score: -20
Time Limit Exceeded

input:

1000
- 1 999999995
? 895722220
? 622701657484514284
? 749191541
? 760407573
? 256900305987464119
? 366941537
? 606282059898057385
? 242911831452679328
? 62941208393497996
? 635277918903264521
? 364101078
? 668570749
? 782177832606476483
? 488263309
? 846845755610111030
? 683601827513277887
? 5323761...

output:

-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
41 165
28 635
1 1
1 412
1 1
26 635
28 635
1 412
26 635
26 635
1 1
28 635...

result:


Subtask #3:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #6:

score: 0
Time Limit Exceeded

Test #111:

score: 10
Accepted
time: 99ms
memory: 5708kb

input:

300000
? 308230551
? 154394919
? 77796824
? 523232316
? 601650936815206607
? 986805724
? 283169431815882827
? 781223930
? 785380179984309713
? 36818911074958611
? 452850684
? 392810692
? 812929344
? 9753139
? 236758865441063408
? 448106017
? 382652997142237763
? 667762111
? 201388730
? 433119061
? 6...

output:

-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
...

result:

ok ok

Test #112:

score: 0
Accepted
time: 112ms
memory: 5724kb

input:

300000
? 694621109955041627
? 142117945123014130
? 271105710887553798
? 588870805
? 596999104759770886
? 559345155
? 913509137
? 863050204268429730
? 121648910055156360
? 27539423
? 237739281
? 102014055246481880
? 918066897
? 150630127417587162
? 675850416
? 465834639
? 242358214
? 914838785
? 3574...

output:

-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
...

result:

ok ok

Test #113:

score: -10
Time Limit Exceeded

input:

300000
- 594041 389378
+ 771465 5
+ 12646 60
+ 148838 36
+ 30991 56
+ 5527 60
+ 488 60
+ 17980 59
+ 3243 60
+ 846785 5
+ 736073 5
+ 206626 6
+ 258271 6
+ 8314 60
+ 10126 60
+ 574513 5
+ 868009 5
+ 22322 59
+ 6150 60
+ 448626 6
+ 330651 6
+ 308596 6
+ 901966 4
+ 10974 60
+ 6572 60
+ 25046 59
+ 7370 6...

output:

24861 715469
1 1
24249 715469
25045 715469
1 1953994
25089 715469
25081 715469
20881 715469
1 1
1 1953972
1 1944470
1 1906373
11033 715469
11033 715469
25089 715469
24861 715469
25081 715469
1 1951924
1 1953994
1 1953990
1 1
25089 715469
20881 715469
24861 715469
25081 715469
25089 715469
24249 7154...

result:


Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%