Submission #308396

#	Time	Username	Problem	Language	Result	Execution time	Memory
308396		gs18115	Sweeping (JOI20_sweeping)	C++14	100 / 100	9882 ms	1854876 KiB

sweeping

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
pi pos[1500010];
int ng[1500010],gl[1500010],gr[1500010];
struct seg
{
    struct node
    {
        int ind,mid;
        vector<vector<int> >vl,vr;
        vector<int>lf,rg;
        map<int,int>mpl,mpr;
        vector<int>nl,nr;
        inline int ngl(int l)
        {
            int g;
            if(!nl.empty())
                g=nl.back(),nl.pop_back();
            else
                g=lf.size(),lf.eb(l),vl.eb(vector<int>());
            lf[g]=l;
            return mpl[l]=g;
        }
        inline int ngr(int r)
        {
            int g;
            if(!nr.empty())
                g=nr.back(),nr.pop_back();
            else
                g=rg.size(),rg.eb(r),vr.eb(vector<int>());
            rg[g]=r;
            return mpr[r]=g;
        }
        inline void dell(int g)
        {
            vl[g].clear();
            vl[g].shrink_to_fit();
            nl.eb(g);
            return;
        }
        inline void delr(int g)
        {
            vr[g].clear();
            vr[g].shrink_to_fit();
            nr.eb(g);
            return;
        }
        inline void put(int x)
        {
            ng[x]=ind;
            int cl=pos[x].fi;
            int cr=pos[x].se;
            {
                auto it=mpl.find(cl);
                if(it==mpl.end())
                    gl[x]=ngl(cl);
                else
                    gl[x]=it->se;
                vl[gl[x]].eb(x);
            }
            {
                auto it=mpr.find(cr);
                if(it==mpr.end())
                    gr[x]=ngr(cr);
                else
                    gr[x]=it->se;
                vr[gr[x]].eb(x);
            }
            return;
        }
        inline vector<int>pushl(int l)
        {
            if(l>mid)
            {
                vector<int>ret;
                auto it=mpr.end();
                while(it!=mpr.begin())
                {
                    it--;
                    if(it->fi<l)
                        break;
                    int grp=it->se;
                    for(int&t:vr[grp])
                        if(ng[t]==ind)
                            pos[t]=pi(l,rg[grp]),ret.eb(t);
                    delr(grp);
                    mpr.erase(it);
                    it=mpr.end();
                }
                return ret;
            }
            vector<int>gv;
            auto it=mpl.begin();
            int ci=-1,csz=-1;
            while(it!=mpl.end())
            {
                if(it->fi>l)
                    break;
                int grp=it->se;
                if((int)vl[grp].size()>csz)
                    csz=vl[ci=grp].size();
                gv.eb(grp);
                mpl.erase(it);
                it=mpl.begin();
            }
            if(ci==-1)
                return vector<int>();
            lf[ci]=l;
            mpl[l]=ci;
            for(int&t:gv)
            {
                if(t==ci)
                    continue;
                for(int&x:vl[t])
                    if(ng[x]==ind)
                        vl[gl[x]=ci].eb(x);
                dell(t);
            }
            return vector<int>();
        }
        inline vector<int>pushr(int r)
        {
            if(r<mid)
            {
                vector<int>ret;
                auto it=mpl.begin();
                while(it!=mpl.end())
                {
                    if(it->fi>r)
                        break;
                    int grp=it->se;
                    for(int&t:vl[grp])
                        if(ng[t]==ind)
                            pos[t]=pi(lf[grp],r),ret.eb(t);
                    dell(grp);
                    mpl.erase(it);
                    it=mpl.begin();
                }
                return ret;
            }
            vector<int>gv;
            auto it=mpr.end();
            int ci=-1,csz=-1;
            while(it!=mpr.begin())
            {
                it--;
                if(it->fi<r)
                    break;
                int grp=it->se;
                if((int)vr[grp].size()>csz)
                    csz=vr[ci=grp].size();
                gv.eb(grp);
                mpr.erase(it);
                it=mpr.end();
            }
            if(ci==-1)
                return vector<int>();
            rg[ci]=r;
            mpr[r]=ci;
            for(int&t:gv)
            {
                if(t==ci)
                    continue;
                for(int&x:vr[t])
                    if(ng[x]==ind)
                        vr[gr[x]=ci].eb(x);
                delr(t);
            }
            return vector<int>();
        }
    }nd[6000010];
    int tree[12000010];
    int nct;
    inline int nnd(int m)
    {
        nct++;
        nd[nct].ind=nct;
        nd[nct].mid=m;
        return nct;
    }
    inline void init(int n,int s,int e)
    {
        if(s>e)
            return;
        int m=s+(e-s)/2;
        tree[n]=nnd(m);
        if(s==e)
            return;
        init(n*2,s,m-1);
        init(n*2+1,m+1,e);
        return;
    }
    void put(int n,int s,int e,int x)
    {
        int m=s+(e-s)/2;
        if(pos[x].se<m)
            return put(n*2,s,m-1,x);
        if(pos[x].fi>m)
            return put(n*2+1,m+1,e,x);
        nd[tree[n]].put(x);
        return;
    }
    void pushl(int n,int s,int e,int l)
    {
        if(l<=s||l>e)
            return;
        int m=s+(e-s)/2;
        vector<int>pv=nd[tree[n]].pushl(l);
        for(int&t:pv)
            put(n*2+1,m+1,e,t);
        pushl(n*2,s,m-1,l);
        pushl(n*2+1,m+1,e,l);
        return;
    }
    void pushr(int n,int s,int e,int r)
    {
        if(r<s||r>=e)
            return;
        int m=s+(e-s)/2;
        vector<int>pv=nd[tree[n]].pushr(r);
        for(int&t:pv)
            put(n*2,s,m-1,t);
        pushr(n*2,s,m-1,r);
        pushr(n*2+1,m+1,e,r);
        return;
    }
    inline pi print(int x)
    {
        return pi(nd[ng[x]].lf[gl[x]],nd[ng[x]].rg[gr[x]]);
    }
}st;
int pct;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;
    cin>>n>>m>>q;
    vector<int>cpv;
    for(int i=0;i++<m;)
    {
        cin>>pos[i].fi>>pos[i].se;
        pos[i].se=n-pos[i].se;
        cpv.eb(pos[i].fi),cpv.eb(pos[i].se);
    }
    vector<pi>qv;
    pct=m;
    for(int i=0;i<q;i++)
    {
        int t,l;
        cin>>t>>l;
        if(t==2)
            cpv.eb(l=n-l);
        else if(t==3)
            cpv.eb(l);
        else if(t==4)
        {
            pos[++pct].fi=l;
            cin>>pos[pct].se;
            pos[pct].se=n-pos[pct].se;
            cpv.eb(pos[pct].fi),cpv.eb(pos[pct].se);
        }
        qv.eb(t,l);
    }
    sort(all(cpv));
    cpv.erase(unique(all(cpv)),cpv.end());
    for(int i=0;i++<pct;)
        pos[i].fi=lower_bound(all(cpv),pos[i].fi)-cpv.begin(),
        pos[i].se=lower_bound(all(cpv),pos[i].se)-cpv.begin();
    int cn=cpv.size();
    st.init(1,0,cn-1);
    for(int i=0;i++<m;)
        st.put(1,0,cn-1,i);
    pct=m;
    for(pi&t:qv)
    {
        if(t.fi==1)
        {
            pi p=st.print(t.se);
            cout<<cpv[p.fi]<<' '<<(n-cpv[p.se])<<'\n';
        }
        else if(t.fi==2)
            st.pushl(1,0,cn-1,(int)(lower_bound(all(cpv),t.se)-cpv.begin()));
        else if(t.fi==3)
            st.pushr(1,0,cn-1,(int)(lower_bound(all(cpv),t.se)-cpv.begin()));
        else
            st.put(1,0,cn-1,++pct);
    }
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25