제출 #1362135

#제출 시각아이디문제언어결과실행 시간메모리
1362135SmuggingSpunEscape Route 2 (JOI24_escape2)C++20
100 / 100
696 ms135092 KiB
#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
typedef long long ll;
const ll INF = 1e18;
template<class T>bool minimize(T& a, T b){
  if(a > b){
    a = b;
    return true;
  }
  return false;
}
const int lim = 1e5 + 5;
int n, t, q;
vector<pair<int, int>>g[lim];
namespace sub12{
  void solve(){
    vector<vector<pair<int, int>>>query(n);
    for(int i = 0; i < q; i++){
      int l, r;
      cin >> l >> r;
      query[l].push_back(make_pair(r, i));
    }
    vector<ll>ans(q, INF);
    for(int l = 1; l < n; l++){
      ll ct = 0;
      sort(query[l].begin(), query[l].end(), greater<pair<int, int>>());
      for(auto& [sa, sb] : g[l]){
        ll ct = sb;
        for(int r = l + 1, ptr = int(query[l].size()) - 1; r <= n; r++){
          while(ptr > -1 && query[l][ptr].first == r){
            minimize(ans[query[l][ptr--].second], ct - sa);
          }
          int d = ct / t, re = ct % t;
          ct = INF;
          for(auto& [a, b] : g[r]){
            minimize(ct, ll(d + int(re > a)) * t + b);
          }
        }
      }
    }
    for(ll& x : ans){
      cout << x << "\n";
    }
  }
}
const int LG = 17;
namespace sub3{
  vector<ll>up[LG];
  ll go(ll ct, int p, int bit){
    if(ct % t > g[p][0].first){
      ct += t - ct % t;
    }
    else{
      ct -= ct % t;
    }
    return ct + up[bit][p];
  }
  void solve(){
    up[0].resize(n);
    for(int i = 1; i < n; i++){
      up[0][i] = g[i][0].second;
    }
    for(int i = 1; i < LG; i++){
      up[i].resize(n);
      for(int j = 1; j + (1 << i) <= n; j++){
        up[i][j] = go(up[i - 1][j], j + (1 << (i - 1)), i - 1);
      }
    }
    for(int _ = 0; _ < q; _++){
      int l, r;
      cin >> l >> r;
      ll ct = 0;
      int init_l = l;
      for(int i = LG - 1; i > -1; i--){
        if(l + (1 << i) <= r){
          ct = go(ct, l, i);
          l += 1 << i;
        }
      }
      cout << ct - g[init_l][0].first << "\n";
    }
  }
}
namespace sub4{
  vector<vector<ll>>up[LG];
  ll go(ll ct, int a, ll delta){
    if(ct % t > a){
      ct += t - ct % t;
    }
    else{
      ct -= ct % t;
    }
    return ct + delta;
  }
  void solve(){
    up[0].resize(n);
    for(int i = 1; i < n; i++){
      up[0][i].resize(g[i].size());
      for(int j = 0; j < g[i].size(); j++){
        up[0][i][j] = g[i][j].second;
      }
    }
    for(int bit = 1; bit < LG; bit++){
      up[bit].resize(n);
      for(int i = 1; i + (1 << bit) <= n; i++){
        up[bit][i].assign(g[i].size(), INF);
        for(int j = 0, k = i + (1 << (bit - 1)); j < g[i].size(); j++){
          for(int h = 0; h < g[k].size(); h++){
            minimize(up[bit][i][j], go(up[bit - 1][i][j], g[k][h].first, up[bit - 1][k][h]));
          }
        }
      }
    }
    for(int _ = 0; _ < q; _++){
      int l, r;
      cin >> l >> r;
      ll ans = INF;
      for(int i = 0; i < g[l].size(); i++){
        ll ct = 0;
        for(int bit = LG - 1, pl = l; bit > -1; bit--){
          if(pl + (1 << bit) <= r){
            if(pl == l){
              ct = up[bit][l][i];
            }
            else{
              ll nt = INF;
              for(int j = 0; j < g[pl].size(); j++){
                minimize(nt, go(ct, g[pl][j].first, up[bit][pl][j]));
              }
              ct = nt;
            }
            pl += 1 << bit;
          }
        }
        minimize(ans, ct - g[l][i].first);
      }
      cout << ans << "\n";
    }
  }
}
namespace sub56{
  const int SIZE = 136;
  vector<vector<ll>>val[LG];
  vector<ll>off_val[lim];
  vector<vector<int>>to[LG];
  vector<pair<int, int>>offline[lim];
  ll off_min[lim];
  void solve(){
    for(int i = 1; i < n; i++){
      sort(g[i].begin(), g[i].end());
    }
    for(int bit = 0; bit < LG; bit++){
      val[bit].resize(n);
      to[bit].resize(n); 
      for(int i = 1; i + (1 << bit) < n; i++){
        val[bit][i].resize(g[i].size());
        to[bit][i].resize(g[i].size());
      }
    }
    for(int i = 1; i + 1 < n; i++){
      vector<int>pf(g[i + 1].size()), sf(g[i + 1].size() + 1);
      sf.back() = -1;
      for(int j = int(g[i + 1].size()) - 1; j > -1; j--){
        sf[j] = sf[j + 1] == -1 || g[i + 1][j].second < g[i + 1][sf[j + 1]].second ? j : sf[j + 1];
      }
      fill(val[pf[0] = 0][i].begin(), val[0][i].end(), INF);
      for(int j = 1; j < g[i + 1].size(); j++){
        pf[j] = g[i + 1][j].second < g[i + 1][pf[j - 1]].second ? j : pf[j - 1];
      }
      for(int j = 0; j < g[i].size(); j++){
        int p = lower_bound(g[i + 1].begin(), g[i + 1].end(), make_pair(g[i][j].second, -1)) - g[i + 1].begin() - 1; 
        if(p > -1){
          val[0][i][j] = t + g[i + 1][to[0][i][j] = pf[p]].second - g[i][j].second;
        }
        if(sf[p + 1] != -1 && minimize(val[0][i][j], ll(g[i + 1][sf[p + 1]].second) - g[i][j].second)){
          to[0][i][j] = sf[p + 1];
        }
      }
    }
    for(int bit = 1; bit < LG; bit++){
      for(int i = 1; i + (1 << bit) < n; i++){
        for(int j = 0; j < g[i].size(); j++){
          to[bit][i][j] = to[bit - 1][i + (1 << (bit - 1))][to[bit - 1][i][j]];
          val[bit][i][j] = val[bit - 1][i][j] + val[bit - 1][i + (1 << (bit - 1))][to[bit - 1][i][j]];
        }
      }
    }
    vector<ll>ans(q, INF);
    for(int qid = 0; qid < q; qid++){
      int l, r;
      cin >> l >> r;
      if(g[l].size() < SIZE){
        for(int i = 0; i < g[l].size(); i++){
          ll sum = g[l][i].second - g[l][i].first;
          for(int bit = LG - 1, p = l, re = i; bit > -1; bit--){
            if(p + (1 << bit) < r){
              sum += val[bit][p][re];
              re = to[bit][p][re];
              p += 1 << bit;
            }
          }
          minimize(ans[qid], sum);
        }
      }
      else{
        offline[l].push_back(make_pair(r, qid));
      }
    }
    for(int l = 1; l < n; l++){
      if(!offline[l].empty()){
        for(int i = l; i < n; i++){
          off_val[i].assign(g[i].size(), INF);
        }
        for(int i = 0; i < g[l].size(); i++){
          off_val[l][i] = g[l][i].second - g[l][i].first;
        }
        for(int i = l; i + 1 < n; i++){
          for(int j = 0; j < g[i].size(); j++){
            minimize(off_val[i + 1][to[0][i][j]], off_val[i][j] + val[0][i][j]);
          }
          off_min[i + 1] = *min_element(off_val[i].begin(), off_val[i].end());
        }
        off_min[n] = *min_element(off_val[n - 1].begin(), off_val[n - 1].end());
        for(auto& [r, qid] : offline[l]){
          ans[qid] = off_min[r];
        }
      }
    }
    for(int i = 0; i < q; i++){
      cout << ans[i] << "\n";
    }
  }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
  cin >> n >> t;
  bool is_sub1234 = true, is_sub13 = true;
  for(int i = 1; i < n; i++){
    int m;
    cin >> m;
    g[i].resize(m);
    for(auto& [a, b] : g[i]){
      cin >> a >> b;
    }
    if(m > 5){
      is_sub1234 = is_sub13 = false;
    }
    else if(m > 1){
      is_sub13 = false;
    }
  }
  cin >> q;
  if(n <= 2000 && is_sub1234){
    sub12::solve();
  }
  else if(is_sub13){
    sub3::solve();
  }
  else if(is_sub1234){
    sub4::solve();
  }
  else{
    sub56::solve();
  }
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:238:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…