QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378230#5449. 楼梯zhouhuanyi0 0ms0kbC++144.5kb2024-04-06 09:56:442024-04-06 09:56:44

Judging History

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

  • [2024-04-06 09:56:44]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [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%