oj.uz

Submission #308396

# Submission time Handle Problem Language Result Execution time Memory
308396 2020-10-01T05:27:47 Z gs18115 Sweeping (JOI20_sweeping) C++14
100 / 100
 9882 ms 1854876 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1035 ms 1457768 KB Output is correct
2 Correct 944 ms 1456760 KB Output is correct
3 Correct 943 ms 1457772 KB Output is correct
4 Correct 944 ms 1457272 KB Output is correct
5 Correct 926 ms 1457016 KB Output is correct
6 Correct 949 ms 1456636 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8222 ms 1736952 KB Output is correct
2 Correct 8055 ms 1755552 KB Output is correct
3 Correct 7953 ms 1750652 KB Output is correct
4 Correct 5982 ms 1673204 KB Output is correct
5 Correct 9785 ms 1854876 KB Output is correct
6 Correct 9882 ms 1791412 KB Output is correct
7 Correct 7737 ms 1723736 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4511 ms 1616820 KB Output is correct
2 Correct 3974 ms 1614164 KB Output is correct
3 Correct 3182 ms 1669960 KB Output is correct
4 Correct 4482 ms 1724088 KB Output is correct
5 Correct 4194 ms 1639392 KB Output is correct
6 Correct 3755 ms 1631028 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4511 ms 1616820 KB Output is correct
2 Correct 3974 ms 1614164 KB Output is correct
3 Correct 3182 ms 1669960 KB Output is correct
4 Correct 4482 ms 1724088 KB Output is correct
5 Correct 4194 ms 1639392 KB Output is correct
6 Correct 3755 ms 1631028 KB Output is correct
7 Correct 6316 ms 1658316 KB Output is correct
8 Correct 6298 ms 1655768 KB Output is correct
9 Correct 6384 ms 1656972 KB Output is correct
10 Correct 5388 ms 1663636 KB Output is correct
11 Correct 7322 ms 1714500 KB Output is correct
12 Correct 6818 ms 1664800 KB Output is correct
13 Correct 6843 ms 1663392 KB Output is correct
14 Correct 1149 ms 1472336 KB Output is correct
15 Correct 3109 ms 1555408 KB Output is correct
16 Correct 6331 ms 1658528 KB Output is correct
17 Correct 5988 ms 1653976 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1035 ms 1457768 KB Output is correct
2 Correct 944 ms 1456760 KB Output is correct
3 Correct 943 ms 1457772 KB Output is correct
4 Correct 944 ms 1457272 KB Output is correct
5 Correct 926 ms 1457016 KB Output is correct
6 Correct 949 ms 1456636 KB Output is correct
7 Correct 8222 ms 1736952 KB Output is correct
8 Correct 8055 ms 1755552 KB Output is correct
9 Correct 7953 ms 1750652 KB Output is correct
10 Correct 5982 ms 1673204 KB Output is correct
11 Correct 9785 ms 1854876 KB Output is correct
12 Correct 9882 ms 1791412 KB Output is correct
13 Correct 7737 ms 1723736 KB Output is correct
14 Correct 4511 ms 1616820 KB Output is correct
15 Correct 3974 ms 1614164 KB Output is correct
16 Correct 3182 ms 1669960 KB Output is correct
17 Correct 4482 ms 1724088 KB Output is correct
18 Correct 4194 ms 1639392 KB Output is correct
19 Correct 3755 ms 1631028 KB Output is correct
20 Correct 6316 ms 1658316 KB Output is correct
21 Correct 6298 ms 1655768 KB Output is correct
22 Correct 6384 ms 1656972 KB Output is correct
23 Correct 5388 ms 1663636 KB Output is correct
24 Correct 7322 ms 1714500 KB Output is correct
25 Correct 6818 ms 1664800 KB Output is correct
26 Correct 6843 ms 1663392 KB Output is correct
27 Correct 1149 ms 1472336 KB Output is correct
28 Correct 3109 ms 1555408 KB Output is correct
29 Correct 6331 ms 1658528 KB Output is correct
30 Correct 5988 ms 1653976 KB Output is correct
31 Correct 5203 ms 1664612 KB Output is correct
32 Correct 7346 ms 1689088 KB Output is correct
33 Correct 4558 ms 1689236 KB Output is correct
34 Correct 8464 ms 1710100 KB Output is correct
35 Correct 8519 ms 1714756 KB Output is correct
36 Correct 6070 ms 1674324 KB Output is correct
37 Correct 9734 ms 1780412 KB Output is correct
38 Correct 7632 ms 1659968 KB Output is correct
39 Correct 7750 ms 1661452 KB Output is correct
40 Correct 6543 ms 1667692 KB Output is correct