Submission #1163028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163028		Math4Life2020	Sweeping (JOI20_sweeping)	C++20	0 / 100	18094 ms	107092 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 = 100; //sparse segtree
mt19937 gen;

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

struct Node { //lazy sparse segtree
    ll xl = -1,xr = -1; 
    map<ll,ll> mem;
    Node(ll _xl, ll _xr) {
        xl = _xl; xr = _xr;
    }
    void apmin(ll minv, ll ul, ll ur) { //apply to [ul,ur]: minv
        for (auto A0: mem) {
            if ((A0).first<=ur) {
                mem[(A0).first]=max((A0).second,minv);
            }
        }
    }
    ll rdpt(ll x) { //read point
       return mem[x];
    }
    void wpt(ll x, ll v) { //write a value of v to the point x
        mem[x]=v;
    }
    ll gfloc(ll bmax, ll vmax) { //find any value among x<=bmax with value <=vmax or return -1
        for (auto A0: mem) {
            if ((A0).first<=bmax && (A0).second<=vmax) {
                return (A0).first;
            }
        }
        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]]);
    }
}

void print(ll rt) {
    return;
    if (rt==-1) {
        return;
    }
    //cout << "printing: rt="<<rt<<"\n";
    //cout << "y="<<y[rt]<<"\n";
    //cout << "l[rt]="<<l[rt]<<", r[rt]="<<r[rt]<<"\n";
    print(l[rt]);
    print(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;
        if (pr.second!=-1) {
            p[pr.second]=-1;
        }
        if (pr.second!=-1) {
            assert(cymin[pr.second]>v0);
        }
        if (rt!=-1 && pr.second!=-1) {
            assert(y[rt]<y[pr.second]);
        }
        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;
        if (pr.first!=-1) {
            p[pr.first]=-1;
        }
        if (cymin[rt]<=v0) {
            cout << "print rt: \n";
            print(rt);
            cout << "print pr.first: \n";
            print(pr.first);
            exit(0);
        }
        assert(cymin[rt]>v0);
        if (pr.first!=-1 && rt!=-1) {
            assert(y[pr.first]<y[rt]);
        }
        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;
    }
    if (y[a]>=y[b]) {
        //cout << "print a:\n";
        print(a);
        //cout << "print b:\n";
        print(b);
        exit(0);
    }
    assert(y[a]<y[b]);
    lft(a);
    lft(b);
    if (ht[a]>=ht[b]) {
        //cout << "fusing a above b\n";
        r[a]=fz(r[a],b);
        p[r[a]]=a;
        lft(a);
        lft(b);
        return a;
    } else {
        //cout << "fusing b above a\n";
        l[b]=fz(a,l[b]);
        p[l[b]]=b;
        lft(a);
        lft(b);
        return b;
    }
}

ll upd(ll rt, ll np) { //root, new point
    if (aset(rt,np)) { //attempt to set
        return rt;
    }
    //cout << "print rt: \n";
    print(rt);
    //cout << "print np: \n";
    print(np);
    pii p0 = cut(rt,y[np]);
    //cout << "p0: "<<p0.first<<","<<p0.second<<"\n";
    //cout << "calling fz from upd\n";
    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;
    //cout << "calling fz from smin\n";
    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];
    lft(rt0);
    ll rt1 = smin(rt0,vpt);
    lft(rt1);
    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);
    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];
    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) {
        if (x0==-1) {
            continue;
        }
        rtn = upd(rtn,x0);
    }
    rootx[x1]=rtn;
    STroot->wpt(x1,cymin[rtn]);
    x[rtn]=x1;
}

void doH(ll xmax, ll htf, ll x1prev=-1) {
    //cout << "doH: xmax="<<xmax<<", htf="<<htf<<"\n";
    ll x1 = STroot->gfloc(xmax-1,htf);
    //cout << "x1="<<x1<<"\n";
    if (x1==-1) {
        return;
    }
    //assert(x1!=x1prev);
    pdn(x1);
    ll r1 = rootx[x1];
    lft(r1);
    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]);
        //assert(cymin[p0.second]>htf);
        x[p0.second]=x1;
        rootx[x1]=p0.second;
    } else {
        STroot->wpt(x1,INF);
        rootx.erase(rootx.find(x1));
    }
    doH(xmax,htf,x1);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N,M,Q; cin >> N >> M >> Q;
    gen = mt19937((long long) new char);
    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);
                assert(ht[p[rt]]>=ht[rt]);
                assert(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