QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378230 | #5449. 楼梯 | zhouhuanyi | 0 | 0ms | 0kb | C++14 | 4.5kb | 2024-04-06 09:56:44 | 2024-04-06 09:56:44 |
answer
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<random>
#define N 300000
using namespace std;
mt19937 RAND(time(0));
long long read()
{
long long sum=0;
char c=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct fhq_treap
{
struct node
{
int ls,rs,cl,rd;
long long sz,dataA,dataB;
};
node tree[20*N+1];
int length;
int new_node(long long sz,int cl)
{
tree[++length]=(node){0,0,cl,(int)(RAND()%1000000000),sz,(!cl)?sz:0,cl?sz:0};
return length;
}
void push_up(int k)
{
tree[k].dataA=tree[tree[k].ls].dataA+tree[tree[k].rs].dataA+((!tree[k].cl)?tree[k].sz:0),tree[k].dataB=tree[tree[k].ls].dataB+tree[tree[k].rs].dataB+(tree[k].cl?tree[k].sz:0);
return;
}
int merge(int x,int y)
{
if (!x||!y) return x^y;
if (tree[x].rd<tree[y].rd)
{
tree[x].rs=merge(tree[x].rs,y),push_up(x);
return x;
}
else
{
tree[y].ls=merge(x,tree[y].ls),push_up(y);
return y;
}
}
void split(int k,long long d,int &x,int &y)
{
if (!k)
{
x=y=0;
return;
}
long long ds;
if (d<=tree[tree[k].ls].dataA) split(tree[k].ls,d,x,tree[k].ls),y=k,push_up(k);
else if (d>=tree[tree[k].ls].dataA+((!tree[k].cl)?tree[k].sz:0)) split(tree[k].rs,d-(tree[tree[k].ls].dataA+((!tree[k].cl)?tree[k].sz:0)),tree[k].rs,y),x=k,push_up(k);
else ds=d-tree[tree[k].ls].dataA,x=new_node(ds,0),y=new_node(tree[k].sz-ds,0),tree[x].ls=tree[k].ls,tree[y].rs=tree[k].rs,push_up(x),push_up(y);
return;
}
void split2(int k,long long d,int &x,int &y)
{
if (!k)
{
x=y=0;
return;
}
long long ds;
if (d<=tree[tree[k].ls].dataB) split2(tree[k].ls,d,x,tree[k].ls),y=k,push_up(k);
else if (d>=tree[tree[k].ls].dataB+(tree[k].cl?tree[k].sz:0)) split2(tree[k].rs,d-(tree[tree[k].ls].dataB+(tree[k].cl?tree[k].sz:0)),tree[k].rs,y),x=k,push_up(k);
else ds=d-tree[tree[k].ls].dataB,x=new_node(ds,1),y=new_node(tree[k].sz-ds,1),tree[x].ls=tree[k].ls,tree[y].rs=tree[k].rs,push_up(x),push_up(y);
return;
}
void split3(int k,long long d,int &x,int &y)
{
if (!k)
{
x=y=0;
return;
}
long long ds;
if (d<=tree[tree[k].ls].dataA+tree[tree[k].ls].dataB) split3(tree[k].ls,d,x,tree[k].ls),y=k,push_up(k);
else if (d>=tree[tree[k].ls].dataA+tree[tree[k].ls].dataB+tree[k].sz) split3(tree[k].rs,d-(tree[tree[k].ls].dataA+tree[tree[k].ls].dataB+tree[k].sz),tree[k].rs,y),x=k,push_up(k);
else ds=d-tree[tree[k].ls].dataA-tree[tree[k].ls].dataB,x=new_node(ds,tree[k].cl),y=new_node(tree[k].sz-ds,tree[k].cl),tree[x].ls=tree[k].ls,tree[y].rs=tree[k].rs,push_up(x),push_up(y);
return;
}
int query(int k,long long x)
{
if (x<=tree[tree[k].ls].dataA+tree[tree[k].ls].dataB) return query(tree[k].ls,x);
else if (x>tree[tree[k].ls].dataA+tree[tree[k].ls].dataB+tree[k].sz) return query(tree[k].rs,x-(tree[tree[k].ls].dataA+tree[tree[k].ls].dataB+tree[k].sz));
else return tree[k].cl;
}
};
fhq_treap T;
char op[N+1];
int m,rt,a[N+1],b[N+1],x[N+1];
long long st[N+1];
long long solve(long long l,long long r,long long q)
{
if (l+1==r) return l*q+1;
long long mid=(l+r)>>1;
if (!T.query(rt,mid*q+1)) return solve(mid,r,q);
else return solve(l,mid,q);
}
int main()
{
freopen("stairs.in","r",stdin);
freopen("stairs.out","w",stdout);
int tmp,x,A,B,C;
long long q,d,ps;
m=read();
for (int i=1;i<=m;++i)
{
cin>>op[i];
if (op[i]=='+')
{
a[i]=read(),b[i]=read(),st[i]=T.tree[rt].dataB;
if (T.tree[rt].dataA<a[i]) rt=T.merge(rt,T.new_node(a[i]-T.tree[rt].dataA,0));
T.split(rt,a[i],A,B),rt=T.merge(T.merge(A,T.new_node(b[i],1)),B);
}
else if (op[i]=='-')
{
a[i]=read(),b[i]=read();
if (a[i]-1<=T.tree[rt].dataA)
{
T.split(rt,a[i]-1,A,tmp),T.split2(tmp,T.tree[tmp].dataB-min((long long)(b[i]),T.tree[tmp].dataB),B,C);
if (a[i]==1) rt=B;
else rt=T.merge(T.merge(A,T.new_node(T.tree[C].dataB,1)),B);
}
}
else if (op[i]=='R')
{
x=read();
for (int j=i-1;j>=i-x;--j)
if (op[j]=='+')
T.split(rt,a[j],A,tmp),T.split2(tmp,b[j],B,C),rt=T.merge(A,C),T.split2(rt,st[j],A,B),rt=A;
}
else
{
q=read();
if (!(T.tree[rt].dataA+T.tree[rt].dataB)) puts("-1 -1");
else d=(T.tree[rt].dataA+T.tree[rt].dataB-1)/q,ps=solve(0,d,q),T.split3(rt,ps+q-1,tmp,C),T.split3(tmp,ps,A,B),printf("%lld %lld\n",T.tree[A].dataA,T.tree[C].dataB),rt=T.merge(T.merge(A,B),C);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
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:
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
Dangerous Syscalls
Test #111:
score: 0
Dangerous Syscalls
input:
300000 ? 308230551 ? 154394919 ? 77796824 ? 523232316 ? 601650936815206607 ? 986805724 ? 283169431815882827 ? 781223930 ? 785380179984309713 ? 36818911074958611 ? 452850684 ? 392810692 ? 812929344 ? 9753139 ? 236758865441063408 ? 448106017 ? 382652997142237763 ? 667762111 ? 201388730 ? 433119061 ? 6...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
0%