QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#318002#5449. 楼梯catagory#0 83ms4100kbC++232.4kb2024-01-30 10:15:422024-07-04 03:21:46

Judging History

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

  • [2024-07-04 03:21:46]
  • 评测
  • 测评结果:0
  • 用时:83ms
  • 内存:4100kb
  • [2024-01-30 10:15:42]
  • 提交

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(' ');}

#define PLL pair<LL,LL>
#define mp(a,b) make_pair(a,b)
#define fir first
#define sec second
const long long N = 300000+95;
long long T;vector<PLL>vc,tr[N];LL n;

void add(LL a,LL b){
  vector<PLL>nt;LL SUM=0;
  for(LL i=0;i<SZ(vc);i++){
    LL l=SUM+1,r=SUM+vc[i].fir;SUM+=vc[i].fir;
    if(r<a)nt.push_back(mp(vc[i].fir,vc[i].sec));
    else if(l<=a&&a<=r){
      nt.push_back(mp(a-l+1,b));
      nt.push_back(mp((r-a),vc[i].sec));
    }
    else nt.push_back(mp(vc[i].fir,vc[i].sec));
  }
  if(SUM<a)nt.push_back(mp(a-SUM,b));
  vc=nt;return ;
}
void del(LL a,LL b){
  add(a-1,b);
  while(SZ(vc)&&vc.back().sec<=b){b-=vc.back().sec;vc.pop_back();}
  if(SZ(vc))vc.back().sec-=b;
  return ;
}
int main(){
  T=read();
  for(LL TC=1;TC<=T;TC++){
    char opt;cin>>opt;
    if(opt=='+'){
      LL a=read(),b=read();
      add(a,b);
    }
    else if(opt=='-'){
      LL a=read(),b=read();
      del(a,b);
    }
    else if(opt=='R'){
      LL u=read();
      vc=tr[TC-u-1];
    }
    else if(opt=='?'){
      LL q=read();q++;PLL ans=mp(-1,-1);LL fl=0;
      for(LL i=0;i<SZ(vc)&&(!fl);i++){
	LL SUM=0;
	for(LL j=i;j<SZ(vc)&&(!fl);j++){
	  LL l=SUM+2,r=SUM+vc[i].fir+vc[j].sec;
	  if(l<=q&&q<=r){
	    //	    cout<<" - > i = "<<i<<" j = "<<j<<" l = "<<l<<" r = "<<r<<endl;
	    LL x=0,y=0;
	    for(LL k=0;k<i;k++)x+=vc[k].fir;
	    for(LL k=SZ(vc)-1;k>j;k--)y+=vc[k].sec;
	    LL X=min(((q-1)-SUM),vc[i].fir);
	    LL Y=min((q-(SUM+X)),vc[i].sec);
	    //	    cout<<" x = "<<x<<" y = "<<y<<" X = "<<X<<" Y = "<<Y<<endl;
	    ans=mp(x+(vc[i].fir-X+1),y+(vc[j].sec-Y+1));fl=1;break;
	  }
	  SUM+=vc[j].sec;
	  if(j+1<SZ(vc))SUM+=vc[j+1].fir;
	}
      }
      if(!fl){puts("-1 -1");continue;}
      writecs(ans.fir);writeln(ans.sec);
      /*      for(LL i=0;i<SZ(vc);i++)
	cout<<" i = "<<i<<" vc[i].fir = "<<vc[i].fir<<" vc[i].sec = "<<vc[i].sec<<endl;
	cout<<endl;*/
    }
    tr[TC]=vc;
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 4100kb

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:

wrong answer query 159: expected 23 but got 22

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Time Limit Exceeded

Test #111:

score: 10
Accepted
time: 68ms
memory: 3632kb

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: 83ms
memory: 3768kb

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:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%