Submission #1131451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131451		huutuan	Escape Route 2 (JOI24_escape2)	C++20	100 / 100	2460 ms	346432 KiB

Main

#include<bits/stdc++.h>

using namespace std;

using ll=long long;

#ifdef sus
const int N=21, LG=5, S=4;
#else
const int N=1e5+10, LG=17, S=700;
#endif
int rjump[LG][N], pos[N], lcost[LG][N];
ll rcost[LG][N], ljump[LG][N];
int jump[N/S+10][N];
ll cost[N/S+10][N], mem[N][N/S+10];
int nxt[N];
vector<pair<int, int>> v;
int n, t, q;
vector<pair<int, int>> edge[N];

ll get_rcost(int l, int r, int idl){
   int d=r-l;
   int cur=idl;
   ll ans=0;
   for (int k=0; k<LG; ++k) if (d>>k&1){
      ans+=rcost[k][cur];
      cur=rjump[k][cur];
   }
   int j=v[cur].second;
   return ans+edge[r][j].second-edge[r][j].first;
}

ll get_lcost(int l, int r, int idr){
   int d=r-l;
   int cur=idr;
   ll ans=0;
   for (int k=0; k<LG; ++k) if (d>>k&1){
      ans+=lcost[k][cur];
      cur=ljump[k][cur];
   }
   int j=v[cur].second;
   return ans+edge[l][j].second-edge[l][j].first;
}

ll get_cost(int l, int r, int idl){
   int d=r-l;
   int cur=jump[d][idl];
   int j=v[cur].second;
   return cost[d][idl]+edge[r][j].second-edge[r][j].first;
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n >> t;
   for (int i=1; i<n; ++i){
      int m; cin >> m;
      vector<pair<int, int>> tmp(m);
      for (auto &j:tmp) cin >> j.first >> j.second;
      sort(tmp.begin(), tmp.end(), [&](pair<int, int> x, pair<int, int> y){
         return make_pair(x.first, -x.second)<make_pair(y.first, -y.second);
      });
      for (auto &j:tmp){
         while (edge[i].size() && edge[i].back().second>=j.second) edge[i].pop_back();
         edge[i].push_back(j);
      }
      pos[i]=v.size();
      for (int j=0; j<(int)edge[i].size(); ++j) v.emplace_back(i, j);
   }
   for (int id=0; id<(int)v.size(); ++id){
      jump[0][id]=id;
      cost[0][id]=0;
   }
   for (int id=0; id<(int)v.size(); ++id){
      int i=v[id].first, j=v[id].second;
      if (i==n-1) break;
      int i2=i+1;
      int j2=lower_bound(edge[i2].begin(), edge[i2].end(), make_pair(edge[i][j].second, -1))-edge[i2].begin();
      j2%=(int)edge[i2].size();
      rcost[0][id]=edge[i2][j2].first>=edge[i][j].second?edge[i2][j2].first-edge[i][j].first:edge[i2][j2].first-edge[i][j].first+t;
      rjump[0][id]=pos[i2]+j2;
      jump[1][id]=rjump[0][id];
      cost[1][id]=rcost[0][id];
   }
   for (int k=2; k<N/S+10; ++k){
      for (int id=0; id<(int)v.size(); ++id){
         if (v[id].first+k>n-1) break;
         jump[k][id]=jump[1][jump[k-1][id]];
         cost[k][id]=cost[k-1][id]+cost[1][jump[k-1][id]];
      }
   }
   for (int k=1; k<LG; ++k){
      for (int id=0; id<(int)v.size(); ++id){
         if (v[id].first+(1<<k)>n-1) break;
         rjump[k][id]=rjump[k-1][rjump[k-1][id]];
         rcost[k][id]=rcost[k-1][id]+rcost[k-1][rjump[k-1][id]];
      }
   }
   for (int id=(int)v.size()-1; id>=0; --id){
      int i=v[id].first, j=v[id].second;
      if (i==1) break;
      int i2=i-1;
      int j2=lower_bound(edge[i2].begin(), edge[i2].end(), make_pair(-1, edge[i][j].first+1), [&](pair<int, int> x, pair<int, int> y){
         return make_pair(x.second, x.first)<make_pair(y.second, y.first);
      })-edge[i2].begin();
      j2=(j2+(int)edge[i2].size()-1)%(int)edge[i2].size();
      lcost[0][id]=edge[i2][j2].second<=edge[i][j].first?edge[i][j].second-edge[i2][j2].second:edge[i][j].second-edge[i2][j2].second+t;
      ljump[0][id]=pos[i2]+j2;
   }
   for (int k=1; k<LG; ++k){
      for (int id=(int)v.size()-1; id>=0; --id){
         if (v[id].first-(1<<k)<1) break;
         ljump[k][id]=ljump[k-1][ljump[k-1][id]];
         lcost[k][id]=lcost[k-1][id]+lcost[k-1][ljump[k-1][id]];
      }
   }
   nxt[n]=n;
   for (int i=n-1; i>=1; --i){
      if ((int)edge[i].size()<S) nxt[i]=i;
      else nxt[i]=nxt[i+1];
   }
   memset(mem, -1, sizeof mem);
   cin >> q;
   while (q--){
      int l, r; cin >> l >> r;
      --r;
      ll ans=1e18;
      if (nxt[l]<=r){
         int i=nxt[l];
         for (int j=pos[i]; j<pos[i]+(int)edge[i].size(); ++j) ans=min(ans, get_lcost(l, i, j)+get_rcost(i, r, j)-edge[i][j-pos[i]].second+edge[i][j-pos[i]].first);
      }else{
         int d=r-l;
         if (mem[l][d]!=-1) ans=mem[l][d];
         else{
            for (int i=pos[l]; i<pos[l]+(int)edge[l].size(); ++i) ans=min(ans, get_cost(l, r, i));
            mem[l][d]=ans;
         }
      }
      cout << ans << '\n';
   }
   return 0;
}

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