제출 #1286031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286031		Math4Life2020	Lottery (JOI25_lottery)	C++17	16 / 100	2944 ms	2162688 KiB

lottery

#include "lottery.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll MXV = 2147483647;

ll v2(ll x) {
    if (x==0) {
        return 100;
    }
    return __builtin_ctz(x);
}

ll l2(ll x) {
    if (x==0) {
        return 100;
    }
    return (31-__builtin_clz(x));
}


struct Node {
    Node *l=nullptr, *r=nullptr;
    ll xl=0,xr=MXV;
    pii pa={0LL,0LL}, pb={0LL,0LL}; //number/sum red/blue ("a/b")
    Node() {
        xl = 0; xr = MXV;
    }
    Node(ll _xl, ll _xr) {
        xl = _xl; xr = _xr;
    }
    pii lpa() {
        if (l==nullptr) {
            return {0LL,0LL};
        } else {
            return l->pa;
        }
    }
    pii lpb() {
        if (l==nullptr) {
            return {0LL,0LL};
        } else {
            return l->pb;
        }
    }
    void upd(ll v, bool isa) { //increase at value v
        if (v<xl || v>xr) {
            return;
        }
        assert(xl<=v && v<=xr);
        //cerr << "xl="<<xl<<", xr="<<xr<<"\n";
        if (xl==xr) {
            assert(xl==v);
            if (isa) {
                pa = {pa.first+1,pa.second+v};
            } else {
                pb = {pb.first+1,pb.second+v};
            }
            return;
        }
        ll m = (xl+xr)/2;
        if (v<=m) {
            if (l==nullptr) {
                l = new Node(xl,m);
            }
            l->upd(v,isa);
        } else {
            if (r==nullptr) {
                r = new Node(m+1,xr);
            }
            r->upd(v,isa);
        }
        if (isa) {
            pa = {pa.first+1,pa.second+v};
        } else {
            pb = {pb.first+1,pb.second+v};
        }
        return;
    }
};

const ll Nm = 262144; const ll E = 18;

ll stmn[2*Nm]; //segtree of min numbers (total capacity)

Node* st[2*Nm];

ll qrmn(ll l, ll r) {
    if (l>r) {
        return (MXV+5); //infinity
    }
    ll vl = v2(l); ll vr = v2(r+1);
    if (vl<vr) {
        return min(qrmn(l+(1LL<<vl),r),stmn[(l>>vl)+(1LL<<(E-vl))]);
    } else {
        return min(qrmn(l,r-(1LL<<vr)),stmn[(r>>vr)+(1LL<<(E-vr))]);
    }
}

void plst(ll i, ll x, ll y) {
    ll p = i+Nm;
    stmn[p]=x+y;
    st[p]->upd(x,0);
    st[p]->upd(y,1);
    p=p/2;
    do {
        stmn[p]=min(stmn[2*p],stmn[2*p+1]);
        st[p]->upd(x,0);
        st[p]->upd(y,1);
        p=p/2;
    } while (p>0);
}

void init(int N, int Q, vector<int> X, vector<int> Y) {
    for (ll i=0;i<(2*Nm);i++) {
        st[i]=new Node();
    }
    for (ll i=0;i<N;i++) {
        plst(i,X[i],Y[i]);
    }
}

int max_prize(int l, int r) {
    ll l1=l; ll r1=r;
    vector<Node*> vn;
    while (l1<=r1) {
        ll vl = v2(l1); ll vr = v2(r1+1);
        if (vl<vr) {
            vn.push_back(st[(l1>>vl)+(1LL<<(E-vl))]);
            l1 += (1LL<<vl);
        } else {
            vn.push_back(st[(r1>>vr)+(1LL<<(E-vr))]);
            r1 -= (1LL<<vr);
        }
    }
    ll K = vn.size();
    ll xl = 0; ll xr = MXV;
    pii pta={0LL,0LL}, ptb={0LL,0LL};
    while (xl<xr) { //searching for: smallest one that DOES NOT work
        ll xm = (xl+xr)/2;
        pii pna=pta, pnb=ptb;
        for (ll k=0;k<K;k++) {
            if (vn[k]!=nullptr) {
                pii pnap = (vn[k]->lpa());
                pii pnbp = (vn[k]->lpb());
                pna={pna.first+pnap.first,pna.second+pnap.second};
                pnb={pnb.first+pnbp.first,pnb.second+pnbp.second};
            }
        }
        ll vla = (r-l+1-pna.first)*xm+pna.second;
        ll vlb = (r-l+1-pnb.first)*xm+pnb.second;
        ll vt = ((r-l+1)/2)*xm;
        if (vla>=vt && vlb>=vt) {
            //pass: go right
            pta = pna; ptb = pnb;
            xl = xm+1;
            for (ll k=0;k<K;k++) {
                if (vn[k]!=nullptr) {
                    vn[k]=vn[k]->r;
                }
            }
        } else {
            //fail: go left
            xr = xm;
            for (ll k=0;k<K;k++) {
                if (vn[k]!=nullptr) {
                    vn[k]=vn[k]->l;
                }
            }
        }
    }
    return (int)min((xl-1),qrmn(l,r));
}

• Subtask 1: 16 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 19
• Subtask 4: 0 / 12
• Subtask 5: 0 / 14
• Subtask 6: 0 / 23