Submission #1162937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162937		Math4Life2020	Sweeping (JOI20_sweeping)	C++20	0 / 100	10 ms	20032 KiB

sweeping

#include <bits/stdc++.h>
using namespace std;

using ll = long long; using pii = pair<ll,ll>;
const ll Qm = 15e5+5; const ll INF = 1e18;
const ll Nm = (1<<30); const ll Em = 30; //sparse segtree
mt19937 gen;

ll v2(ll x) {
    return __builtin_ctz(x);
}

struct Node { //lazy sparse segtree
    ll xl = -1,xr = -1; 
    ll lzmin = -INF; //lazy tag NOT APPLIED already
    //value = max(current value, lzmin)
    ll stmin = INF;
    Node *cl = nullptr,*cr=nullptr; //child left / right
    Node(ll _xl, ll _xr) {
        xl = _xl; xr = _xr;
    }
    void pdnst() { //push down segtree element
        if (stmin==INF) {
            lzmin = -INF;
            return;
        }
        if (lzmin>stmin) {
            stmin = lzmin;
            if (cl!=nullptr) {
                cl->lzmin = max(cl->lzmin,lzmin);
            }
            if (cr!=nullptr) {
                cr->lzmin = max(cr->lzmin,lzmin);
            }
        }
        lzmin = -INF;
    }
    void apmin(ll minv, ll ul, ll ur) { //apply to [ul,ur]: minv
        pdnst();
        if (ur<xl || ul>xr) {
            return;
        }
        if (stmin==INF || minv<=lzmin) {
            return;
        }
        if (ul<=xl && ur>=xr) {
            lzmin = max(lzmin,minv);
            return;
        } else {
            if (cl!=nullptr) {
                cl->apmin(minv,ul,ur);
            }
            if (cr!=nullptr) {
                cr->apmin(minv,ul,ur);
            }
            stmin = INF;
            if (cl!=nullptr) {
                stmin = min(stmin,cl->stmin);
            }
            if (cr!=nullptr) {
                stmin = min(stmin,cr->stmin);
            }
        }
    }
    ll rdpt(ll x) { //read point
        pdnst();
        if (xl==x && xr==x) {
            if (stmin==INF) {
                return -INF;
            }
            return stmin;
        } else {
            ll xm = (xl+xr-1)/2;
            if (x<=xm) {
                if (cl==nullptr) {
                    cl = new Node(xl,xm);
                }
                return cl->rdpt(x);
            } else {
                if (cr==nullptr) {
                    cr = new Node(xm+1,xr);
                }
                return cr->rdpt(x);
            }
        }
    }
    void wpt(ll x, ll v) { //write a value of v to the point x
        pdnst();
        if (xl==x && xr==x) {
            lzmin = -INF;
            stmin = v;
            return;
        } else {
            ll xm = (xl+xr-1)/2;
            if (x<=xm) {
                if (cl==nullptr) {
                    cl = new Node(xl,xm);
                }
                cl->wpt(x,v);
            } else {
                if (cr==nullptr) {
                    cr = new Node(xm+1,xr);
                }
                cr->wpt(x,v);
            }
            stmin = INF;
            if (cl!=nullptr) {
                stmin = min(stmin,cl->stmin);
            }
            if (cr!=nullptr) {
                stmin = min(stmin,cr->stmin);
            }
            lzmin = -INF;
        }
    }
    ll gfloc(ll bmax, ll vmax) { //find any value among x<=bmax with value <=vmax or return -1
        pdnst();
        if (xl>bmax || stmin>vmax) {
            return -1;
        }
        if (xl==xr) {
            if (stmin<=vmax) {
                return xl;
            } else {
                return -1;
            }
        }
        if (cl!=nullptr) {
            ll v1 = cl->gfloc(bmax,vmax);
            if (v1!=-1) {
                return v1;
            }
        }
        if (cr!=nullptr) {
            ll v1 = cr->gfloc(bmax,vmax);
            if (v1!=-1) {
                return v1;
            }
        }
        return -1;
    }
};
Node* STroot;

ll l[Qm]; //treap left child (lower y)
ll r[Qm]; //treap right (higher y)
ll p[Qm]; //treap parent
ll ht[Qm]; //randomized binary search tree height
ll y[Qm]; //y-value (key)
ll x[Qm]; //x-value (store only for parents)
ll sz[Qm]; //treap size of subtree
ll cymin[Qm]; //child y-min of subtree
map<ll,ll> rootx; //x of root -> root value if exists

ll dsuf[Qm];

ll getf(ll x1) {
    if (dsuf[x1]==x1) {
        return x1;
    }
    return (dsuf[x1]=getf(dsuf[x1]));
}

void lft(ll rt) {
    if (rt==-1) {
        return;
    }
    sz[rt]=1;
    cymin[rt]=y[rt];
    if (l[rt]!=-1) {
        p[l[rt]]=rt;
        sz[rt]+=sz[l[rt]];
        cymin[rt]=min(cymin[rt],cymin[l[rt]]);
    }
    if (r[rt]!=-1) {
        p[r[rt]]=rt;
        sz[rt]+=sz[r[rt]];
        cymin[rt]=min(cymin[rt],cymin[r[rt]]);
    }
}

pii cut(ll rt, ll v0) { //cut at root: y<=v0 go into left, y>v0 go into right
    if (rt==-1) {
        return {-1,-1};
    }
    if (y[rt]<=v0) {
        pii pr = cut(r[rt],v0);
        r[rt]=pr.first;
        lft(rt);
        lft(pr.first);
        lft(pr.second);
        p[rt]=-1;
        p[pr.second]=-1;
        return {rt,pr.second};
    } else {
        pii pr = cut(l[rt],v0);
        l[rt]=pr.second;
        lft(rt);
        lft(pr.first);
        lft(pr.second);
        p[rt]=-1;
        p[pr.first]=-1;
        return {pr.first,rt};
    }
}

bool aset(ll rt, ll np) { //attempt to set, 1->valid, 0->invalid
    if (rt==-1) {
        return 0;
    }
    if (y[rt]==y[np]) {
        dsuf[np]=rt;
        return 1;
    } else if (y[np]<y[rt]) {
        if (l[rt]==-1) {
            return 0;
        }
        return aset(l[rt],np);
    } else {
        if (r[rt]==-1) {
            return 0;
        }
        return aset(r[rt],np);
    }
}

ll fz(ll a, ll b) { //assume y[all terms in a] < y[all terms in b]
    //cout << "fusing a,b="<<a<<","<<b<<"\n";
    if (a==-1) {
        return b;
    }
    if (b==-1) {
        return a;
    }
    lft(a);
    lft(b);
    if (ht[a]>=ht[b]) {
        //cout << "fusing a above b\n";
        r[a]=fz(r[a],b);
        lft(a);
        lft(b);
        return a;
    } else {
        //cout << "fusing b above a\n";
        l[b]=fz(l[b],a);
        lft(a);
        lft(b);
        return b;
    }
}

ll upd(ll rt, ll np) { //root, new point
    if (aset(rt,np)) { //attempt to set
        return rt;
    }
    pii p0 = cut(rt,y[np]);
    ll rf = fz(fz(p0.first,np),p0.second);
    x[rf]=x[rt];
    return rf;
}

ll smin(ll rt, ll vt) { //set min to vt, return new root
    //cout << "smin(rt="<<rt<<",vt="<<vt<<")\n";
    pii p0 = cut(rt,vt);
    //cout << "p0="<<p0.first<<","<<p0.second<<"\n";
    if (p0.first==-1) {
        return rt;
    }
    queue<ll> qpr;
    qpr.push(p0.first);
    while (!qpr.empty()) {
        ll x0 = qpr.front(); qpr.pop();
        //cout << "x0 in qpr: "<<x0<<"\n";
        dsuf[x0]=p0.first;
        if (l[x0]!=-1) {
            qpr.push(l[x0]);
        }
        if (r[x0]!=-1) {
            qpr.push(r[x0]);
        }
    }
    l[p0.first]=-1;
    r[p0.first]=-1;
    sz[p0.first]=1;
    y[p0.first]=vt;
    p[p0.first]=-1;
    cymin[p0.first]=vt;
    ll rf = fz(p0.first,p0.second);
    x[rf]=x[rt];
    lft(rf);
    return rf;
}

void pdn(ll x1) {
    ll vpt = STroot->rdpt(x1);
    //cout << "vpt="<<vpt<<"\n";
    if (rootx.find(x1)==rootx.end()) {
        return;
    }
    ll rt0 = rootx[x1];
    ll rt1 = smin(rt0,vpt);
    rootx[x1]=rt1;
    x[rt1]=x1;
}

void put(ll x1, ll rtn) { //merge thing with root rtn into x1
    //cout << "put rtn="<<rtn<<" into "<<x1<<"\n";
    pdn(x1);
    lft(x1);
    lft(rtn);
    if (rtn==-1) {
        return;
    }
    x[rtn]=x1;
    if (rootx.find(x1)==rootx.end()) {
        rootx[x1]=rtn;
        x[rtn]=x1;
        rootx[x1]=rtn;
        STroot->wpt(x1,cymin[rtn]);
        //cout << "setting x1,cymin="<<x1<<","<<cymin[rtn]<<"\n";
        return;
    }
    ll rt0 = rootx[x1];
    lft(rt0);
    if (sz[rt0]>sz[rtn]) {
        swap(rt0,rtn);
    } //thus sz[rt0]<=sz[rtn]
    queue<ll> q0;
    vector<ll> v0;
    q0.push(rt0);
    while (!q0.empty()) {
        ll ptt = q0.front(); q0.pop();
        v0.push_back(ptt);
        if (l[ptt]!=-1) {
            q0.push(l[ptt]);
        }
        if (r[ptt]!=-1) {
            q0.push(r[ptt]);
        }
    }
    for (ll x0: v0) {
        rtn = upd(rtn,x0);
    }
    rootx[x1]=rtn;
    STroot->wpt(x1,cymin[rtn]);
    x[rtn]=x1;
}

void doH(ll xmax, ll htf) {
    //cout << "doH: xmax="<<xmax<<", htf="<<htf<<"\n";
    ll x1 = STroot->gfloc(xmax-1,htf);
    //cout << "x1="<<x1<<"\n";
    if (x1==-1) {
        return;
    }
    pdn(x1);
    ll r1 = rootx[x1];
    pii p0 = cut(r1,htf);
    //cout << "p0 upon cutting: "<<p0.first<<","<<p0.second<<"\n";
    if (p0.first==-1) {
        return;
    }
    put(xmax,p0.first);
    if (p0.second!=-1) {
        //cout << "write ymin: "<<cymin[p0.second]<<"\n";
        STroot->wpt(x1,cymin[p0.second]);
        x[p0.second]=x1;
        rootx[x1]=p0.second;
    } else {
        STroot->wpt(x1,INF);
        rootx.erase(rootx.find(x1));
    }
    doH(xmax,htf);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N,M,Q; cin >> N >> M >> Q;
    gen = mt19937(123456789);
    STroot = new Node(0,Nm-1);
    for (ll q=0;q<Qm;q++) {
        dsuf[q]=q;
    }
    for (ll m=0;m<M;m++) {
        ll x1,y1; cin >> x1 >> y1;
        l[m]=-1;
        r[m]=-1;
        p[m]=-1;
        ht[m]=gen();
        y[m]=y1;
        x[m]=x1;
        sz[m]=1;
        cymin[m]=y1;
        put(x1,m);
    }
    ll ndust = M;
    for (ll q=0;q<Q;q++) {
        ll t1; cin >> t1;
        if (t1==1) {
            ll pc; cin >> pc; pc--;
            pc = getf(pc);
            //cout << "pc="<<pc<<"\n";
            ll rt = pc;
            while (p[rt]!=-1) {
                assert(l[p[rt]]==rt || r[p[rt]]==rt);
                rt = p[rt];
            }
            ll xc = x[rt];
            pdn(xc);
            pc = getf(pc);
            cout << xc << " " << y[pc] <<"\n";
        } else if (t1==2) {
            ll wc; cin >> wc;
            doH(N-wc,wc);
        } else if (t1==3) {
            ll wc; cin >> wc;
            STroot->apmin(N-wc,0,wc);
        } else {
            ll x1,y1; cin >> x1 >> y1;
            ll m = ndust;
            l[m]=-1;
            r[m]=-1;
            p[m]=-1;
            ht[m]=gen();
            y[m]=y1;
            x[m]=x1;
            sz[m]=1;
            cymin[m]=y1;
            put(x1,m);
            ndust++;
        }
    }
}

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