Submission #1047218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047218		heeew	Sweeping (JOI20_sweeping)	C++14	100 / 100	3643 ms	1216388 KiB

sweeping

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

const int MAX_Q=1000010;

struct Obj
{
    int x,d,i;
    bool operator < (const Obj &o) const
    {
        if(x!=o.x)return x<o.x;
        return d<o.d;
    }
};

struct Segtree
{
    struct Seg
    {
        int xi,yi;
        Seg()
        {
            xi=yi=MAX_Q;
        }
        void upd(int d,int i)
        {
            if(d==0) xi=i;
            else yi=i;
        }
    };
    int sz;
    vector<Obj> obj;
    vector<Seg> seg;
    void merge_(Seg &p,const Seg &l,const Seg &r)
    {
        p.xi=l.xi;
        if(l.yi>r.xi)p.xi=min(p.xi,r.xi);
        p.yi=r.yi;
        if(r.xi>l.yi)p.yi=min(p.yi,l.yi);
    }
    void init_seg(int i,int s,int e)
    {
        if(s+1==e)
        {
            seg[i].upd(obj[s].d,obj[s].i);
            return;
        }
        init_seg(i<<1,s,(s+e)>>1);
        init_seg(i<<1|1,(s+e)>>1,e);
        merge_(seg[i],seg[i<<1],seg[i<<1|1]);
    }
    Seg find_(int i,int s,int e,int l,int r)
    {
        if(s>=r || e<=l)return {};
        if(l<=s && e<=r)return seg[i];
        Seg v;
        merge_(v,find_(i<<1,s,(s+e)>>1,l,r),find_(i<<1|1,(s+e)>>1,e,l,r));
        return v;
    }
    int findx(int i,int s,int e,int l,int r,Seg j)
    {
        if(s>=r || e<=l)return -1;
        if(l<=s && e<=r && seg[i].xi>=j.yi)return -1;
        if(s+1==e)return s;
        Seg j2;
        merge_(j2,j,find_(i<<1,s,(s+e)>>1,l,r));
        int v=findx(i<<1|1,(s+e)>>1,e,l,r,j2);
        if(v!=-1)return v;
        return findx(i<<1,s,(s+e)>>1,l,r,j);
    }
    int findy(int i,int s,int e,int l,int r,Seg j)
    {
        if(s>=r || e<=l)return -1;
        if(l<=s && e<=r && seg[i].yi>=j.xi)return -1;
        if(s+1==e)return s;
        Seg j2;
        merge_(j2,find_(i<<1|1,(s+e)>>1,e,l,r),j);
        int v=findy(i<<1,s,(s+e)>>1,l,r,j2);
        if(v!=-1)return v;
        return findy(i<<1|1,(s+e)>>1,e,l,r,j);
    }
    void init_()
    {
        sz=obj.size();
        sort(obj.begin(),obj.end());
        seg.resize(sz<<2);
        init_seg(1,0,sz);
        Seg v;
    }
    pii calc(pii p)
    {
        int lx=p.first,rx=p.second;
        int l=lower_bound(obj.begin(),obj.end(),(Obj){lx,0,0})-obj.begin();
        int r=upper_bound(obj.begin(),obj.end(),(Obj){rx,1,0})-obj.begin();
        int fx=findx(1,0,sz,l,r,(Seg){});
        int fy=findy(1,0,sz,l,r,(Seg){});
        if(fx!=-1)
            lx=obj[fx].x;
        if(fy!=-1)
            rx=obj[fy].x;
        return {lx,rx};
    }
};

struct Ask
{
    pii p;
    int l,r;
};

int n,m,q;
vector<pii> pos;
vint pin;
vector<Obj> qry;
vector<Ask> ask;
Segtree sseg[MAX_Q<<2];

void init_(int i,int s,int e)
{
    if(s==e)return;
    if(s+1==e)
    {
        sseg[i].obj.push_back(qry[s]);
        sseg[i].init_();
        return;
    }
    init_(i<<1,s,(s+e)>>1);
    init_(i<<1|1,(s+e)>>1,e);
    for(auto o : sseg[i<<1].obj)
        sseg[i].obj.push_back(o);
    for(auto o : sseg[i<<1|1].obj)
        sseg[i].obj.push_back(o);
    sseg[i].init_();
}

pii calc(int i,int s,int e,int l,int r,pii p)
{
    if(s>=r || e<=l)return p;
    if(l<=s && e<=r)return sseg[i].calc(p);
    return calc(i<<1|1,(s+e)>>1,e,l,r,calc(i<<1,s,(s+e)>>1,l,r,p));
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m >> q;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin >> x >> y;
        pos.push_back({x,n-y});
        pin.push_back(0);
    }
    for(int i=0;i<q;i++)
    {
        int t,x,y;
        cin >> t >> x;
        if(t==1)
        {
            ask.push_back({pos[x-1],pin[x-1],(int)qry.size()});
        }
        else if(t==2)
            qry.push_back({n-x,0,(int)qry.size()});
        else if(t==3)
            qry.push_back({x,1,(int)qry.size()});
        else
        {
            cin >> y;
            pos.push_back({x,n-y});
            pin.push_back(qry.size());
        }
    }
    int qn=qry.size();
    init_(1,0,qn);
    for(auto a : ask)
    {
        pii p=calc(1,0,qn,a.l,a.r,a.p);
        cout << p.first << ' ' << n-p.second << '\n';
    }
    return 0;
}

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