QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#318641#5449. 楼梯catagory0 112ms5912kbC++233.7kb2024-01-31 16:32:492024-01-31 16:32:50

Judging History

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

  • [2024-01-31 16:32:50]
  • 评测
  • 测评结果:0
  • 用时:112ms
  • 内存:5912kb
  • [2024-01-31 16:32:49]
  • 提交

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

#define ull unsigned long long
namespace GenHelper{
  ull seed=19260817ull;
  void Get(){
    seed^=(seed<<7);
    seed^=(seed>>11);
    seed^=(seed<<13);
    return ;
  }
  ull Rand(){Get();return (seed^(seed<<32ull));}
}using GenHelper::Rand;
#define random(a,b) (Rand()%(b-a+1)+a)

void solve(LL x,LL y,LL q){
  LL p=GET(x,y);assert((p%q)==0);
  if(p==q){writecs(x);writeln(y);return ;}
  LL K=(p/q);LL k=(K>>1)*q;
  vector<LL>ord={0,1};
  if(random(0,1))swap(ord[0],ord[1]);
  for(auto op:ord){
    if(!op){//x
      LL l=x,r=lim,ans=-1;
      while(l<=r){
	LL mid=(l+r)>>1;
	if(GET(mid,y)>=k){l=mid+1;ans=mid;}
	else {r=mid-1;}
      }
      if(ans!=-1&&GET(ans,y)==k){solve(ans,y,q);return ;}
    }
    else {//y
      LL l=y,r=lim,ans=-1;
      while(l<=r){
	LL mid=(l+r)>>1;
	if(GET(x,mid)>=(p-k)){l=mid+1;ans=mid;}
	else {r=mid-1;}
      }
      if(ans!=-1&&GET(x,ans)==(p-k)){solve(x,ans,q);return ;}
    }
  }
  assert(0);return ;
}

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;
	}*/
      solve(1,1,q);
    }
    __rt[t]=rt;
  }
  return 0;
}

詳細信息

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 10
Accepted
time: 24ms
memory: 5872kb

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: -10
Runtime Error

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:


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: 112ms
memory: 5912kb

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: 71ms
memory: 5568kb

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:

25061 709605
1 1
24919 696445
25061 714997
1 1953994
25089 715469
25081 715469
21551 696445
1 1
1 1953972
1 1944470
1 1906373
22393 268661
22393 268661
25089 715469
25061 709605
25081 715469
1 1951924
1 1953994
1 1953990
1 1
25089 715469
21551 696445
25061 709605
25081 715469
25089 715469
24919 6964...

result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%