Submission #1151601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151601		byunjaewoo	Escape Route 2 (JOI24_escape2)	C++20	54 / 100	3096 ms	201428 KiB

Main

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

const int N=100010, L=17, B=100, INF=1e18;
int n, t, q, rt[N];
vector<int> nxt[L][N], sum[L][N], dist[N], dist2[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_clz(x); i>=0; i--) if(x&(1<<i)) {
        ret.second+=sum[i][p][ret.first], ret.first=nxt[i][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;
        for(int j=0; j<L; j++) nxt[j][i].resize(v[i].size()), sum[j][i].resize(v[i].size());
    }
    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][i][j]=0, sum[0][i][j]=t+v[i+1][0].first-v[i][j].first;
        }
        else {
            nxt[0][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][i][j]=v[i+1][nxt[0][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][i][j]=nxt[k-1][i+(1<<(k-1))][nxt[k-1][i][j]];
        sum[k][i][j]=sum[k-1][i][j]+sum[k-1][i+(1<<(k-1))][nxt[k-1][i][j]];
    }
    for(int i=n-1, p=0; i>=1; i--) {
        if(v[i].size()<=B) p=i;
        else if(p) {
            rt[i]=p;
            dist[i].resize(v[p].size(), INF);
            for(int j=0; j<v[i].size(); j++) {
                pair<int, int> tmp=f(i, p, j);
                dist[i][tmp.first]=min(dist[i][tmp.first], tmp.second);
            }
        }
        else rt[i]=n+1;
    }
    for(int i=1; i<n; i++) if(v[i].size()>=B) {
        vector<pair<int, int>> tmp;
        for(int j=0; j<v[i].size(); j++) tmp.push_back({j, 0});
        bool flag=false;
        for(int j=i+1; j<=n; j++) {
            if(v[j].size()<B && flag) break;
            flag|=(v[j].size()<B);
            int mn=INF;
            for(int k=0; k<v[i].size(); k++) mn=min(mn, tmp[k].second+v[j-1][tmp[k].first].second-v[j-1][tmp[k].first].first);
            dist2[i].push_back(mn);
            if(j==n) break;
            for(int k=0; k<v[i].size(); k++) {
                tmp[k].second+=sum[0][j-1][tmp[k].first], tmp[k].first=nxt[0][j-1][tmp[k].first];
            }
        }
    }
    cin>>q;
    while(q--) {
        int l, r; cin>>l>>r;
        int ret=INF;
        if(v[l].size()<=B) {
            for(int i=0; i<v[l].size(); i++) ret=min(ret, g(l, r, i));
            cout<<ret<<"\n"; continue;
        }
        if(rt[l]<r) {
            int p=rt[l];
            for(int i=0; i<v[p].size(); i++) ret=min(ret, g(p, r, i)+dist[l][i]);
            cout<<ret<<"\n"; continue;
        }
        cout<<dist2[l][r-l-1]<<"\n";
    }
    return 0;
}

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