QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#318641 | #5449. 楼梯 | catagory | 0 | 112ms | 5912kb | C++23 | 3.7kb | 2024-01-31 16:32:49 | 2024-01-31 16:32:50 |
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::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%