제출 #1285265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285265		Math4Life2020	Lottery (JOI25_lottery)	C++20	0 / 100	5130 ms	591252 KiB

lottery

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

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

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

map<ll,ll> mer[2*Nm]; //segtree: map of red endpoints
map<ll,ll> meb[2*Nm]; //blue endpoints
vector<pair<ll,pii>> mtr[2*Nm]; //total red
vector<pair<ll,pii>> mtb[2*Nm]; //total blue

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));
}

void init(int N, int Q, vector<int> X, vector<int> Y) {
    for (ll i=0;i<N;i++) {
        stmn[Nm+i]=X[i]+Y[i];
        ll p = (Nm+i)/2;
        do {
            stmn[p]=min(stmn[2*p],stmn[2*p+1]);
            p=p/2;
        } while (p>0);
    }
    for (ll i=0;i<N;i++) {
        ll p = (Nm+i);
        do {
            if (mer[p].find(X[i])==mer[p].end()) {
                mer[p][X[i]]=0;
            }
            mer[p][X[i]]++;
            if (meb[p].find(Y[i])==meb[p].end()) {
                meb[p][Y[i]]=0;
            }
            meb[p][Y[i]]++;
            p=p/2;
        } while (p>0);
    }
    for (ll p=1;p<(2*Nm);p++) {
        ll sz = (1LL<<(E-l2(p)));
        mtr[p].push_back({0LL,{0LL,sz}});
        ll xc = 0;
        ll mc = sz;
        ll yc = 0;
        for (pii p0: mer[p]) {
            ll xn = p0.first;
            yc = mc*(xn-xc)+yc;
            xc = xn;
            mc = mc - p0.second;
            mtr[p].push_back({xc,{yc,mc}});
        }
    }
     for (ll p=1;p<(2*Nm);p++) {
        ll sz = (1LL<<(E-l2(p)));
        mtb[p].push_back({0LL,{0LL,sz}});
        ll xc = 0;
        ll mc = sz;
        ll yc = 0;
        for (pii p0: meb[p]) {
            ll xn = p0.first;
            yc = mc*(xn-xc)+yc;
            xc = xn;
            mc = mc - p0.second;
            mtb[p].push_back({xc,{yc,mc}});
        }
    }
}

ll qrmn(ll l, ll r) {
    if (l>r) {
        return (1LL<<31); //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))]);
    }
}

ll qelr(ll p, ll qrv) {
    //cout << "qelb: p="<<p<<", qrv="<<qrv<<"\n";
    auto A0 = lower_bound(mtr[p].begin(),mtr[p].end(),(pair<ll,pii>){qrv,{-1LL,-1LL}});
    if (A0==mtr[p].end()) {
        A0--;
        pair<ll,pii> p0 = *A0;
        return ((p0.second.first)+(qrv-p0.first)*p0.second.second);
    }
    pair<ll,pii> p0 = *A0;
    if (p0.first==qrv) {
        //cout << (p0.second.first) << "\n";
        return p0.second.first;
    }
    A0--;
    p0 = *A0;
    //cout << ((p0.second.first)+(qrv-p0.first)*p0.second.second) << "\n"; 
    return ((p0.second.first)+(qrv-p0.first)*p0.second.second);
} 

ll qsumr(ll l, ll r, ll qrv) {
    if (l>r) {
        return 0;
    }
    ll vl = v2(l); ll vr = v2(r+1);
    if (vl<vr) {
        return (qsumr(l+(1LL<<vl),r,qrv)+qelr((l>>vl)+(1LL<<(E-vl)),qrv));
    } else {
        return (qsumr(l,r-(1LL<<vr),qrv)+qelr((r>>vr)+(1LL<<(E-vr)),qrv));
    }
}

ll qelb(ll p, ll qrv) {
    //cout << "qelb: p="<<p<<", qrv="<<qrv<<"\n";
    auto A0 = lower_bound(mtb[p].begin(),mtb[p].end(),(pair<ll,pii>){qrv,{-1LL,-1LL}});
    if (A0==mtb[p].end()) {
        A0--;
        pair<ll,pii> p0 = *A0;
        return ((p0.second.first)+(qrv-p0.first)*p0.second.second);
    }
    pair<ll,pii> p0 = *A0;
    if (p0.first==qrv) {
        //cout << (p0.second.first) << "\n";
        return p0.second.first;
    }
    A0--;
    p0 = *A0;
    //cout << ((p0.second.first)+(qrv-p0.first)*p0.second.second) << "\n"; 
    return ((p0.second.first)+(qrv-p0.first)*p0.second.second);
}

ll qsumb(ll l, ll r, ll qrv) {
    if (l>r) {
        return 0;
    }
    ll vl = v2(l); ll vr = v2(r+1);
    if (vl<vr) {
        return (qsumb(l+(1LL<<vl),r,qrv)+qelb((l>>vl)+(1LL<<(E-vl)),qrv));
    } else {
        return (qsumb(l,r-(1LL<<vr),qrv)+qelb((r>>vr)+(1LL<<(E-vr)),qrv));
    }
}

int max_prize(int l, int r) { //0-indexed
    ll minv = 0;
    ll maxv = qrmn(l,r);
    //cout << "maxv0="<<maxv<<"\n";
    while (minv!=maxv) {
        ll qrv = (minv+maxv+1)/2;
        ll tgt = ((ll)(r-l+1)/2)*qrv;
        if (qsumr(l,r,qrv)>=tgt && qsumb(l,r,qrv)>=tgt) {
            minv = qrv;
        } else {
            maxv = qrv-1;
        }
    }
    return minv;
}

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