QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#318627 | #5449. 楼梯 | catagory | 0 | 103ms | 3680kb | C++23 | 2.8kb | 2024-01-31 16:21:02 | 2024-01-31 16:21:02 |
Judging History
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::query(rt,x)-x+1);
LL Y=(seg::get(rt,y)-y+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++)
for(LL j=1;j<=Y&&!fl;j++)
if(GET(i,j)==q){writecs(i);writeln(j);fl=1;break;}
}
__rt[t]=rt;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
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:
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: 100ms
memory: 3668kb
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: 103ms
memory: 3680kb
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%