Submission #1155205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155205		Math4Life2020	Escape Route 2 (JOI24_escape2)	C++20	14 / 100	3097 ms	102672 KiB

Main

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

using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 131072; const ll E = 17; const ll INF = 1e18;

ll len[Nm]; //time (length) from index
pii intv[Nm];
pii bjumpR[Nm][E]; //reverse bjump
//{new jump index, time (end to end)}
pii bjumpF[Nm][E]; //forward bjump
ll IND = 0;

inline pii fz(pii p1, pii p2) {
    if (p1.first<p2.first) {
        return p1;
    }
    return p2;
}

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

inline ll l2(ll x) {
    return (31-__builtin_clz(x));
}

pii stm[2*Nm];

pii gmin(ll a, ll b) {
    if (a>b) {
        return {INF,INF};
    }
    ll va = v2(a); ll vb = v2(b+1);
    if (va<vb) {
        return fz(stm[(a>>va)+(1<<(E-va))],gmin(a+(1<<va),b));
    } else {
        return fz(stm[(b>>vb)+(1<<(E-vb))],gmin(a,b-(1<<vb)));
    }
}

ll grd(ll i0, ll d) {
    assert(d>=0);
    if (d==0) {
        return 0;
    }
    //ll ld = l2(d);
    ll ld = 0;
    return (grd(bjumpR[i0][ld].first,d-(1<<ld))+bjumpR[i0][ld].second);
}

ll gfd(ll i0, ll d) {
    assert(d>=0);
    if (d==0) {
        return 0;
    }
    //ll ld = l2(d);
    ll ld = 0;
    return (gfd(bjumpF[i0][ld].first,d-(1<<ld))+bjumpF[i0][ld].second);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N,T; cin >> N >> T;
    vector<pii> rng[N];
    vector<ll> idx[N];
    map<ll,ll> sind[N]; //start time -> index
    map<ll,ll> eind[N]; //end time -> index 
    for (ll i=0;i<(N-1);i++) {
        ll M; cin >> M;
        multiset<ll> sl; //set of lefts
        vector<pii> vba;
        vector<pii> vnew;
        for (ll tc=0;tc<M;tc++) {
            ll a,b; cin >> a >> b;
            vba.push_back({b,a});
            sl.insert(a);
        }
        sort(vba.rbegin(),vba.rend());
        for (pii p0: vba) {
            ll xl = *(--sl.end());
            vnew.push_back({xl,p0.first});
            sl.erase(sl.find(p0.second));
        }
        sort(vnew.begin(),vnew.end());
        ll xlc = -1;
        for (pii p0: vnew) {
            if (p0.first!=xlc) {
                rng[i].push_back(p0);
            }
            xlc = p0.first;
        }
        stm[i+Nm]={rng[i].size(),i};
        assert(rng[i].size()>=1);
        for (pii p0: rng[i]) {
            //cout << "i="<<i<<"; rng elem="<<p0.first<<","<<p0.second<<"\n";
            //cout << "IND="<<IND<<"\n";
            sind[i][p0.first]=IND;
            eind[i][p0.second]=IND;
            idx[i].push_back(IND);
            intv[IND]={p0.first,p0.second};
            len[IND] = p0.second-p0.first;
            IND++;
        }
        assert(idx[i].size()==rng[i].size());
    }
    for (ll p=(Nm-1);p>=1;p--) {
        stm[p]=fz(stm[2*p],stm[2*p+1]);
    }
    for (ll i=0;i<N;i++) {
        for (ll x=0;x<rng[i].size();x++) {
            ll cind = idx[i][x];
            pii p0 = rng[i][x];
            //cout << "i,x,cind="<<i<<","<<x<<","<<cind<<"\n";
            if (i<(N-2)) {
                auto A0 = sind[i+1].lower_bound(p0.second);
                if (A0==sind[i+1].end()) {
                    A0 = sind[i+1].begin();
                    ll nind = (*A0).second;
                    bjumpF[cind][0]={nind,intv[nind].second-intv[cind].second+T};
                } else {
                    ll nind = (*A0).second;
                    bjumpF[cind][0]={nind,intv[nind].second-intv[cind].second};
                }
            } else {
                bjumpF[cind][0]={0,0};
            }
            if (i>0) {
                //cout << "i="<<i<<", p0="<<p0.first<<", "<<p0.second<<"\n";
                auto A0 = eind[i-1].upper_bound(p0.first);
                if (A0==eind[i-1].begin()) {
                    A0 = eind[i-1].end();
                    A0--;
                    ll nind = (*A0).second;
                    //cout << "f2nind = "<<nind<<"\n";
                    bjumpR[cind][0]={nind,-intv[nind].first+intv[cind].first+T};
                    //cout << "r value: "<<bjumpR[cind][0].second<<"\n";
                } else {
                    A0--;
                    ll nind = (*A0).second;
                    //cout << "f1nind = "<<nind<<"\n";
                    bjumpR[cind][0]={nind,-intv[nind].first+intv[cind].first};
                    //cout << "r value: "<<bjumpR[cind][0].second<<"\n";
                }
            } else {
                bjumpR[cind][0]={0,0};
            }
        }
    }
    for (ll i=0;i<Nm;i++) {
        for (ll e=1;e<E;e++) {
            pii pxf = bjumpF[i][e-1];
            bjumpF[i][e]={bjumpF[pxf.first][e-1].first,bjumpF[pxf.first][e-1].second+pxf.second};
            pii pxr = bjumpR[i][e-1];
            bjumpR[i][e]={bjumpR[pxr.first][e-1].first,bjumpR[pxr.first][e-1].second+pxr.second};
        }
    }
    ll Q; cin >> Q;
    map<pii,ll> AMEM;
    for (ll q=0;q<Q;q++) {
        ll l,r; cin >> l >> r;
        l--; r--;
        if (AMEM.find({l,r})!=AMEM.end()) {
            cout << AMEM[{l,r}] << "\n";
            continue;
        }
        ll ans = INF;
        //ll xmax = gmin(l,r-1).second;
        ll xmax = l;
        //cout << "xmax="<<xmax<<"\n";
        for (ll idx0: idx[xmax]) {
            //cout << "idx0="<<idx0<<"\n";
            //cout << "terms: "<<grd(idx0,xmax-l)<<","<<gfd(idx0,r-1-xmax)<<","<<len[idx0]<<"\n";
            ans = min(ans,grd(idx0,xmax-l)+gfd(idx0,r-1-xmax)+len[idx0]);
        }
        AMEM[{l,r}]=ans;
        cout << ans << "\n";
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 17
• Subtask 4: 0 / 23
• Subtask 5: 0 / 36
• Subtask 6: 0 / 10