제출 #1210046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210046		mychecksedad	Railway Trip (JOI17_railway_trip)	C++20	25 / 100	341 ms	128680 KiB

railway_trip

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e5+100, M = 1e5+10, K = 21, MX = 30;

struct Fenwick{
  vector<int> t;
  Fenwick(int n){
    t.resize(n + 1);
  }
  void add(int v){
    while(v < t.size()){
      t[v]++;
      v += v & -v;
    }
  }
  int get(int v){
    int res=0;
    while(v > 0){
      res+=t[v];
      v -= v&-v;
    }
    return res;
  }
};


int n, k, q, a[N], d[N], rmq[N][K];
vector<pii> g[N];
vector<pii> A[N][21];

int get(int l, int r){
  int k = __lg(r-l+1);
  return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
}

void solve(){
  cin >> n >> k >> q;
  vector<vi> C(k + 1);
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
    C[a[i]].pb(i);
    rmq[i][0] = a[i];
  }

  for(int j = 1; j < K; ++j){
    for(int i = 1; i + (1<<j) <= n + 1; ++i){
      rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
    }
  }

  Fenwick fw(n);
  for(int i = k; i >= 1; --i){
    for(int x: C[i]) fw.add(x);
    for(int j = 0; j < C[i].size(); ++j){
      d[C[i][j]] = fw.get(C[i][j]);
    }
  }
  vector<pii> Q;
  vector<int> W(n + 1);
  int w = 1;
  for(int i = 1; i <= n; ++i){
    while(Q.size() && Q.back().ff <= a[i]) Q.pop_back();
    if(Q.size()){
      int v = i;
      int u = Q.back().ss;
      int last_pos = lower_bound(all(C[a[i]]), i) - C[a[i]].begin();
      if(last_pos > 0 && C[a[i]][last_pos - 1] > u){
        W[i] = W[C[a[i]][last_pos - 1]] + 1;
      }else{
        W[i] = 1;
      }
      g[v].pb({u, W[i]});
    }
    Q.pb({a[i], i});
  }
  Q.clear();
  w = 1;
  for(int i = n; i >= 1; --i){
    while(Q.size() && Q.back().ff <= a[i]) Q.pop_back();
    if(Q.size()){
      int v = i;
      int u = Q.back().ss;
      int last_pos = upper_bound(all(C[a[i]]), i) - C[a[i]].begin();
      if(last_pos < C[a[i]].size() && C[a[i]][last_pos] < u){
        W[i] = W[C[a[i]][last_pos]] + 1;
      }else{
        W[i] = 1;
      }
      g[v].pb({u, W[i]});
    }else
      W[i] = 0;
    Q.pb({a[i], i});
  }

  vector<bool> USED(n + 1);
  for(int i = 1; i <= n; ++i){
    priority_queue<pair<int, int>> Q;
    Q.push({0, i});
    vi use;
    while(!Q.empty()){
      int v = Q.top().ss;
      int cur = -Q.top().ff;
      Q.pop();
      if(USED[v]) continue;
      USED[v] = 1;
      A[i][a[v]].pb({v, cur});
      use.pb(v);
      for(auto [u, w_]: g[v]){
        Q.push({- cur - w_, u});
      }
    }
    for(int x: use) USED[x] = 0;
  }
  

  for(int i = 1; i <= q; ++i){
    int l, r; cin >> l >> r;
    if(l > r) swap(l, r);
    int ans = n;
    for(int level = get(l, r); level <= k; ++level){
      for(auto [v, wv]: A[l][level]){
        for(auto [u, wu]: A[r][level]){
          // cerr << wv << ' ' << wu << ' ' << level << ' ' << u << ' ' << v << '\n';
          ans = min(ans, wv + wu + d[max(u, v)] - d[min(u, v)]);
        }
      }
    }
    cout << ans - 1 << '\n';
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 25 / 25
• Subtask 4: 0 / 55