QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#318683 | #5449. 楼梯 | catagory | 0 | 123ms | 5736kb | C++23 | 3.5kb | 2024-01-31 17:00:08 | 2024-01-31 17:00:08 |
Judging History
answer
#include<bits/stdc++.h>
#define LL int
#define SZ(x) ((LL)(x.size()))
using namespace std;
inline 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;
}
#define ll long long
void write(ll x){
if(x<0){putchar('-');x=(-x);}
if(x>9)write(x/10);
putchar('0'+x%10);
}
inline void writeln(ll x){write(x);puts("");}
inline void writecs(ll x){write(x);putchar(' ');}
const int lim = 1000000000;
namespace seg{
const int SIZE = 20000000+95;
struct node{LL l,r;ll 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=0ll){//将小于 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=0ll){//得到其中一列的值
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 int N = 300000+95;
int 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 0;
return (X+Y-1);
}
#define ull unsigned long long
namespace GenHelper{
ull seed=19260817ull;
inline void Get(){
seed^=(seed<<7);
seed^=(seed>>11);
seed^=(seed<<13);
return ;
}
inline 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;
LL l=x,r=lim,ans=lim+1;
while(l<=r){
LL mid=(l+r)>>1;
if(GET(mid,y)>k){l=mid+1;}
else {r=mid-1;ans=mid;}
}
if(GET(ans,y)==k){solve(ans,y,q);return ;}
assert(ans>x);
LL Y=seg::query(rt,ans)+1;
LL c=GET(x,Y);Y+=(c-(p-k));
assert(GET(x,Y)==(p-k));
solve(x,Y,q);return ;
}
int main(){
T=read();
for(LL t=1;t<=T;t++){
char opt;cin>>opt;
if(opt=='+'){
LL a=read();ll b=read();
seg::update(rt,1,a,b);
}
else if(opt=='-'){
LL a=read();ll 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 X=seg::get(rt,1);
ll Y=seg::query(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: 17ms
memory: 5732kb
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: 123ms
memory: 5736kb
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: 107ms
memory: 5676kb
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%