Submission #1155194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155194		Math4Life2020	Escape Route 2 (JOI24_escape2)	C++20	14 / 100	3095 ms	29604 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());
    }
    //TRY HERE INSTEAD
    ll Q; cin >> Q;
    for (ll q=0;q<Q;q++) {
        ll l,r; cin >> l >> r;
        l--; r--;
        ll ans = INF;
        for (ll tind0: idx[l]) {
            ll cind = tind0;
            ll xc = l+1;
            ll tc = intv[cind].second;
            ll tel = len[cind];
            while (xc<r) {
                //cout << "xc,tc="<<xc<<","<<tc<<"\n";
                auto A0 = sind[xc].lower_bound(tc);
                if (A0==sind[xc].end()) {
                    tc -= T;
                    //cout << "lap\n";
                } else {
                    pii p0 = *A0;
                    tel += intv[p0.second].second-tc;
                    tc = intv[p0.second].second;
                    xc++;
                    //cout << "aug\n";
                    cind = p0.second;
                }
            }
            ans = min(ans,tel);
        }
        cout << ans << "\n";
    }
    exit(0);

    // 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 = l;
    //     //ll xmax = gmin(l,r-1).second;
    //     //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