Submission #1285262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285262		Math4Life2020	Lottery (JOI25_lottery)	C++20	Compilation error	0 ms	0 KiB

lottery

#include "lottery.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; 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
map<ll,pii> mtr[2*Nm]; //total red
map<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][0]={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][xc]={yc,mc};
        }
    }
     for (ll p=1;p<(2*Nm);p++) {
        ll sz = (1LL<<(E-l2(p)));
        mtb[p][0]={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][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 = mtr[p].lower_bound(qrv);
    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 = mtb[p].lower_bound(qrv);
    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_price(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;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccymIG4X.o: in function `main':
stub.cpp:(.text.startup+0x25d): undefined reference to `max_prize(int, int)'
collect2: error: ld returned 1 exit status