Submission #1152018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152018		byunjaewoo	Escape Route 2 (JOI24_escape2)	C++20	0 / 100	2 ms	5256 KiB

Main

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

const int N=101000, L=17, B=100, INF=1e18;
int n, t, q, rt[N], bidx[N], dist[N/B][N];
vector<int> idx[N], big;
int num, nxt[L][N], sum[L][N];
vector<pair<int, int>> v[N];

pair<int, int> f(int l, int r, int k) {
    int x=r-l, p=l;
    pair<int, int> ret={k, 0};
    for(int i=31-__builtin_clzll(x); i>=0; i--) if(x&(1<<i)) {
        ret.second+=sum[i][idx[p][ret.first]], ret.first=nxt[i][idx[p][ret.first]];
        p+=(1<<i);
    }
    return ret;
}

int g(int l, int r, int k) {
    if(l>=r) return 0;
    pair<int, int> tmp=f(l, r-1, k);
    return tmp.second+v[r-1][tmp.first].second-v[r-1][tmp.first].first;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>t;
    for(int i=1; i<n; i++) {
        int m; cin>>m;
        while(m--) {
            int a, b; cin>>a>>b;
            v[i].push_back({a, b});
        }
    }
    v[n].push_back({0, 0});
    for(int i=1; i<=n; i++) {
        vector<pair<int, int>> tmp;
        sort(v[i].begin(), v[i].end());
        for(int j=0; j<v[i].size(); j++) {
            while(!tmp.empty() && tmp.back().second>=v[i][j].second) tmp.pop_back();
            tmp.push_back(v[i][j]);
        }
        v[i]=tmp;
        idx[i].resize(v[i].size());
        for(int j=0; j<idx[i].size(); j++) idx[i][j]=++num;
    }
    for(int i=1; i<=n-1; i++) for(int j=0; j<v[i].size(); j++) {
        if(v[i][j].second>v[i+1].back().first) {
            nxt[0][idx[i][j]]=0, sum[0][idx[i][j]]=t+v[i+1][0].first-v[i][j].first;
        }
        else {
            nxt[0][idx[i][j]]=lower_bound(v[i+1].begin(), v[i+1].end(), make_pair(v[i][j].second, 0ll))-v[i+1].begin();
            sum[0][idx[i][j]]=v[i+1][nxt[0][idx[i][j]]].first-v[i][j].first;
        }
    }
    for(int k=1; k<L; k++) for(int i=1; i<n; i++) for(int j=0; j<v[i].size(); j++) if(i+(1<<k)-1<=n) {
        nxt[k][idx[i][j]]=nxt[k-1][idx[i+(1<<(k-1))][nxt[k-1][idx[i][j]]]];
        sum[k][idx[i][j]]=sum[k-1][idx[i][j]]+sum[k-1][idx[i+(1<<(k-1))][nxt[k-1][idx[i][j]]]];
    }
    for(int i=1; i<n; i++) if(v[i].size()>=B) {
        bidx[i]=big.size(), big.push_back(i);
        vector<int> tmp(v[i].size(), 0);
        for(int j=i+1; j<=n; j++) {
            int mn=INF;
            for(int k=0; k<v[j-1].size(); k++) mn=min(mn, tmp[k]+v[j-1][k].second-v[j-1][k].first);
            dist[bidx[i]][j]=mn;
            if(j==n) break;
            vector<int> tmp2(v[j].size(), INF);
            for(int k=0; k<v[j-1].size(); k++)
                tmp2[nxt[0][idx[j-1][k]]]=min(tmp2[nxt[0][idx[j-1][k]]], tmp[k]+sum[0][idx[j-1][k]]);
            tmp=tmp2;
        }
    }
    cin>>q;
    while(q--) {
        int l, r; cin>>l>>r;
        if(v[l].size()<=B) {
            int ret=INF;
            for(int i=0; i<v[l].size(); i++) ret=min(ret, g(l, r, i));
            cout<<ret<<"\n";
        }
        else cout<<dist[bidx[l]][r]<<"\n";
    }
    return 0;
}

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