/ @@18khV /

记录详情

Wrong Answer


  
# 状态 耗时 内存占用
#1 Wrong Answer 成績取消 0ms 0 Bytes

代码

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    //splay
    ll size;
    ll fa[3000000+1];
    ll s[3000000+1][1+1];
    ll sl[3000000+1];
    ll sr[3000000+1];
    ll len[3000000+1];
    //splay
    
    struct splay
    {
        ll root;
        
        ll insert(ll l,ll r)
        {
            size++;
            fa[size]=s[size][0]=s[size][1]=0;
            len[size]=(sr[size]=r)-(sl[size]=l);
            //interval  [l,r) [l,r-1]
            return size;
        }
        
        ll pr(ll l,ll r)
        {
            return (root=insert(l,r));
        }
        
        ll update(ll now)
        {
            return (len[now]=len[s[now][0]]+len[s[now][1]]+sr[now]-sl[now]);
        }
        
        ll dir(ll now)
        {
            //left or right
            return ((s[fa[now]][1]==now)?1:0);
        }
        
        void rotate(ll now)
        {
            ll nowdir=dir(now),nowfa=fa[now];
            fa[now]=fa[nowfa];
            if (nowfa==root)
                root=now;
            else
                s[fa[nowfa]][dir(nowfa)]=now;
            if ((s[nowfa][nowdir]=s[now][nowdir^1])!=0)
                fa[s[nowfa][nowdir]]=nowfa;
            fa[s[now][nowdir^1]=nowfa]=now;
            update(nowfa);
            update(now);
        }
        
        void splay_work(ll now)
        {
            for (;fa[now];rotate(now))
                if (fa[fa[now]]!=0)
                    rotate((dir(now)==dir(fa[now]))?fa[now]:now);
        }
        
        ll split(ll now,ll x)
        {
            x+=sl[now];
            //pre x number not change
            //behind number move to new node
            ll ans=insert(x,sr[now]);
            //ans   new node
            sr[now]=x;
            if (s[now][1]==0)
                fa[s[now][1]=ans]=now;
            else
            {
                ll t;
                //t temp
                for (t=s[now][1];s[t][0]!=0;t=s[t][0])
                    ;
                fa[s[t][0]=ans]=t;
                for (;t!=now;t=fa[t])
                    update(t);
            }
            splay_work(ans);
            return ans;
        }
        
        ll pop(ll x)
        {
            //pop x th number
            ll now,flag;
            for (now=root,flag=1;flag;)
                if (len[s[now][0]]>=x)
                    now=s[now][0];
                else
                {
                    x-=len[s[now][0]];
                    if (x<=sr[now]-sl[now])
                    {
                        if (x!=sr[now]-sl[now])
                            split(now,x);
                        if (x!=1)
                            now=split(now,x-1);
                        flag=0;
                    }
                    else
                    {
                        x-=sr[now]-sl[now];
                        now=s[now][1];
                    }
                }
            splay_work(now);
            //delete
            fa[s[now][0]]=fa[s[now][1]]=0;
            if (s[now][0]==0)
                root=s[now][1];
            else
            {
                ll t;
                //t temp
                for (t=s[now][0];s[t][1]!=0;t=s[t][1])
                    ;
                splay_work(t);
                update(root=fa[s[t][1]=s[now][1]]=t);
            }
            return sl[now];
        }
        
        ll push_back(ll x)
        {
            //push back number x
            ll ans=insert(x,x+1);
            if (root==0)
                return (root=ans);
            else
            {
                ll now;
                for (now=root;s[now][1]!=0;now=s[now][1])
                    ;
                splay_work(now);
                update(fa[s[now][1]=ans]=now);
                return ans;
            }
        }
    };
    
    splay sp[300000+1];
    
    void main()
    {
        ll n,m,q;
        scanf("%lld%lld%lld",&n,&m,&q);
        size=0;
        for (ll i=1;i<=n;i++)
            sp[i].pr((i-1)*m+1,i*m);
        sp[0].pr(m,m+1);
        for (ll i=2;i<=n;i++)
            sp[0].push_back(i*m);
        for (ll i=1;i<=q;i++)
        {
            ll x,y,temp;
            scanf("%lld%lld",&x,&y);
            sp[x].push_back(sp[0].pop(x));
            printf("%lld\n",temp=sp[x].pop(y));
            sp[0].push_back(temp);
        }
    }
};

int main()
{
    dts::main();
}

信息

递交者
类型
递交
题目
P1028 列队
题目数据
下载
语言
C++
递交时间
2020-07-28 16:25:25
评测时间
2023-09-09 03:41:43
评测机
分数
0
总耗时
0ms
峰值内存
0 Bytes