Submission #1152022

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

Main

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

const int N=100010, L=17, B=200, INF=1e18;
int n, t, q, rt[N];
vector<int> idx[N], dist[N], dist2[N];
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_clz(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]]]];
    }
    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;
        }
    }
    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