제출 #1228490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228490		noyancanturk	Escape Route 2 (JOI24_escape2)	C++20	100 / 100	361 ms	79984 KiB

Main

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

#define int int64_t
#define pb push_back

using pii=pair<int,int>;

const int lim=1e5+100;

int jump[20][lim],lift[20][lim];
int p1[lim],p2[lim];
int used[lim];
vector<pii>a[lim];
vector<int>inds[lim];
vector<int>toask[lim];
map<pii,int>anss;
int l[3*lim],r[3*lim];

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n,t;
  cin>>n>>t;
  int tt=1;
  for(int i=0;i<n-1;i++){
    int m;
    cin>>m;
    while(m--){
      int l,r;
      cin>>l>>r;
      a[i].pb({l,r});
      used[tt]=-1;
      inds[i].pb(tt++);
    }
  }
  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    cin>>l[i]>>r[i];
    l[i]--,r[i]--;
    toask[l[i]].pb(r[i]);
  }
  for(int i=n-2;0<=i;i--){
    sort(a[i].begin(),a[i].end());
    for(int j=a[i].size()-2;0<=j;j--){
      if(a[i][j].first==a[i][j+1].first){
        a[i][j+1]=pii{INT_MAX,INT_MAX};
      }
    }
    sort(a[i].begin(),a[i].end());
    while(a[i].back()==pii{INT_MAX,INT_MAX}){
      a[i].pop_back();
    }
    int mini=a[i].back().second;
    for(int j=a[i].size()-2;0<=j;j--){
      if(mini<=a[i][j].second){
        a[i][j]=pii{INT_MAX,INT_MAX};
      }
      mini=min(mini,a[i][j].second);
    }
    sort(a[i].begin(),a[i].end());
    while(a[i].back()==pii{INT_MAX,INT_MAX}){
      a[i].pop_back();
    }
    for(int j=0;j<a[i].size();j++){
      p1[inds[i][j]]=a[i][j].first,p2[inds[i][j]]=a[i][j].second;
    }
    if(i!=n-2){
      int p=a[i+1].size();
      for(int j=a[i].size()-1;0<=j;j--){
        while(p&&a[i][j].second<=a[i+1][p-1].first){
          p--;
        }
        if(p==a[i+1].size()){
          jump[0][inds[i][j]]=inds[i+1][0];
          lift[0][inds[i][j]]=t-a[i][j].first+a[i+1][0].first;
        }else{
          jump[0][inds[i][j]]=inds[i+1][p];
          lift[0][inds[i][j]]=a[i+1][p].first-a[i][j].first;
        }
        for(int k=1;k<20;k++){
          jump[k][inds[i][j]]=jump[k-1][jump[k-1][inds[i][j]]];
          lift[k][inds[i][j]]=lift[k-1][inds[i][j]]+lift[k-1][jump[k-1][inds[i][j]]];
        }
      }
    }
    sort(toask[i].begin(),toask[i].end());
    toask[i].resize(unique(toask[i].begin(),toask[i].end())-toask[i].begin());
    vector<pii>guys;
    for(int j=0;j<a[i].size();j++){
      guys.pb({inds[i][j],0});
    }
    int past=i;
    for(int R:toask[i]){
      int c=R-1-past;
      for(int k=19;0<=k;k--){
        if(c&(1<<k)){
          for(int j=0;j<guys.size();j++){
            guys[j].second+=lift[k][guys[j].first];
            guys[j].first=jump[k][guys[j].first];
          }
        }
      }
      past+=c;
      for(int j=0;j<guys.size();j++){
        if(used[guys[j].first]==-1||guys[j].second<used[guys[j].first]){
          used[guys[j].first]=guys[j].second;
        }
      }
      int ans=LLONG_MAX;
      for(int j=0;j<guys.size();j++){
        if(used[guys[j].first]!=-1){
          guys[j].second=used[guys[j].first];
          used[guys[j].first]=-1;
          ans=min(ans,guys[j].second+p2[guys[j].first]-p1[guys[j].first]);
        }else{
          swap(guys[j],guys.back());
          guys.pop_back();
          j--;
        }
      }
      anss[{i,R}]=ans;
    }
  }
  for(int i=0;i<q;i++){
    cout<<anss[{l[i],r[i]}]<<'\n';
  }
}

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