Submission #1210084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210084		mychecksedad	Railway Trip (JOI17_railway_trip)	C++20	30 / 100	1196 ms	589824 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>
#define cerr if(false) cerr
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], rmq2[N][K], lazy[N];
vector<pii> g[N];
vector<pii> G[N];
vector<pii> A[N][21];
vector<int> ANS(N, MOD);
vector<int> ANS2(N, MOD);
vector<int> ANS3(N, MOD);
vector<int> ANS4(N, MOD);
vector<int> ANS5(N, MOD);
vector<array<int, 3>> Q[N];
vector<array<int, 2>> Q1[N];
vector<array<int, 2>> Q2[N];
vector<array<int, 2>> Q3[N];
vector<array<int, 2>> Q4[N];
set<array<int, 2>> T[N];

int maxc(int x, int y){
  return a[x] >= a[y] ? x : y; // left most
}

int maxc2(int x, int y){
  return a[y] >= a[x] ? y : x; // right most
}

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

int get2(int l, int r){
  int k = int(log2(r-l+1));
  return maxc2(rmq2[l][k], rmq2[r-(1<<k)+1][k]);
}

void add(int l, int r, int lev, int idx){
  if(l > r) return;
  int L = 1, R = r, res = r;
  if(a[get(l, r)] < lev) return;
  while(L <= R){
    int mid = L+R>>1;
    if(a[get(mid, r)] > lev){
      L = mid + 1;
    }else{
      res = mid;
      R = mid - 1;
    }
  }
  if(a[get(res, r)] == lev){
    cerr << get2(res, r) << ' ' << idx << "f\n";
    Q1[get2(res, r)].pb({idx, r+1});
  }
}
void add2(int l, int r, int lev, int idx){
  if(l > r) return;
  int L = l, R = r, res = l;
  if(a[get(l, r)] < lev) return;
  while(L <= R){
    int mid = L+R>>1;
    if(a[get(l, mid)] > lev){
      R = mid - 1;
    }else{
      res = mid;
      L = mid + 1;
    }
  }
  if(a[get(l, res)] == lev){
    Q2[get(l, res)].pb({idx, l-1});
  }
}
void add3(int l, int r, int lev, int idx){
  if(l > r) return;
  int L = 1, R = r, res = r;
  if(a[get(l, r)] < lev) return;
  while(L <= R){
    int mid = L+R>>1;
    if(a[get(mid, r)] > lev){
      L = mid + 1;
    }else{
      res = mid;
      R = mid - 1;
    }
  }
  if(a[get(res, r)] == lev){
    cerr << get2(res, r) << ' ' << idx << "f\n";
    Q3[get2(res, r)].pb({idx, r+1});
  }
}
void add4(int l, int r, int lev, int idx){
  if(l > r) return;
  int L = l, R = r, res = l;
  if(a[get(l, r)] < lev) return;
  while(L <= R){
    int mid = L+R>>1;
    if(a[get(l, mid)] > lev){
      R = mid - 1;
    }else{
      res = mid;
      L = mid + 1;
    }
  }
  if(a[get(l, res)] == lev){
    Q4[get(l, res)].pb({idx, l-1});
  }
}
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] = i;
    rmq2[i][0] = i;
  }

  for(int j = 1; j < K; ++j){
    for(int i = 1; i + (1<<j) <= n + 1; ++i){
      rmq[i][j] = maxc(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
      rmq2[i][j] = maxc2(rmq2[i][j-1], rmq2[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]});
        G[u].pb({v, 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]});
        G[u].pb({v, W[i]});
      }else
        W[i] = 0;
      Q.pb({a[i], i});
    }
  }


  for(int i = 1; i <= q; ++i){
    int l, r; cin >> l >> r;
    if(l > r) swap(l, r);
    int level1 = get(l, r);
    int level2 = get2(l, r);
    Q1[level1].pb({i, l});
    if(a[level1] > a[l])
      add(1, l-1, a[level1], i);
    Q2[level2].pb({i, r});
    if(a[level1] > a[r])
      add2(r+1, n, a[level2], i);

    // cerr << l << ' ' << r << ' ' << level1 << " gg1\n";
    // cerr << l << ' ' << r << ' ' << level2 << " gg2\n";
    if(g[level1].size() == 2){
      int ww = max(a[g[level1][0].ff], a[g[level1][1].ff]);
      // cerr << ww << " fiucll" << '\n';
      add3(1, l-1, ww, i);
      add4(r+1, n, ww, i);
    }
    for(auto [node, W]: g[level1]){ // these nodes are same for level1 and level2
      // cout << l << ' ' << r << ' ' << node << " gg\n";
      Q[node].pb({i, l, r});
    }
  }

  vector<pii> pts;
  for(int i = 1; i <= n; ++i){
    pts.pb({a[i], i});
    lazy[i] = 0;
  }
  sort(all(pts));

  vector<int> done(n + 1);
  for(int i = 1; i <= n; ++i){
    done[i] = g[i].size();
  } 

  for(auto [_, v]: pts){
    int big = -1;
    int ww = 0;
    for(auto [u, w]: G[v]){
      if(big == -1 || T[u].size() > T[big].size()) big = u, ww = w;
    }
    if(big != -1){
      if(done[big] == 1){
        T[v].swap(T[big]);
        --done[big];
      }else{
        T[v] = T[big];
        --done[big];
      }
      lazy[v] = lazy[big] + ww;
    }
    T[v].insert({v, -lazy[v]});
    for(auto [u, w]: G[v]){
      if(u != big){
        --done[u];
        for(auto [node, dist]: T[u]){
          auto it = T[v].lower_bound(array<int,2>{node, -MOD});
          int nw = dist + lazy[u] + w - lazy[v];
          if(it != T[v].end() && (*it)[0] == node){
            if((*it)[1] > nw){
              T[v].erase(it);
              T[v].insert({node, nw});
            }
          }else{
            T[v].insert({node, nw});
          }
        }
      }
    }

    cerr << v << ' ' << lazy[v] << ":\n";
    for(auto [pt, t]: T[v]){
      cerr << pt << ' ' << t << '\n';
    }


    for(auto [idx, pt]: Q1[v]){
      auto it = T[v].lower_bound(array<int, 2>{pt, -MOD});
      assert(it != T[v].end());
      assert((*it)[0] == pt);
      ANS2[idx] = min(ANS2[idx], (*it)[1] + lazy[v] - d[v]);

      cerr << "# " << v << ' ' << idx << ' ' << pt << ' ' << (*it)[1] + lazy[v] << ' ' <<  d[v] << '\n';
    }


    for(auto [idx, pt]: Q2[v]){
      auto it = T[v].lower_bound(array<int, 2>{pt, -MOD});
      assert(it != T[v].end());
      assert((*it)[0] == pt);
      ANS3[idx] = min((*it)[1] + lazy[v] + d[v], ANS3[idx]);
      cerr << "# " << v << ' ' << idx << ' ' << pt << ' ' << (*it)[1] + lazy[v] << ' ' <<  d[v] << '\n';
    }

    for(auto [idx, pt]: Q3[v]){
      auto it = T[v].lower_bound(array<int, 2>{pt, -MOD});
      assert(it != T[v].end());
      assert((*it)[0] == pt);
      ANS4[idx] = min(ANS4[idx], (*it)[1] + lazy[v] - d[v]);

      cerr << "# " << v << ' ' << idx << ' ' << pt << ' ' << (*it)[1] + lazy[v] << ' ' <<  d[v] << '\n';
    }


    for(auto [idx, pt]: Q4[v]){
      auto it = T[v].lower_bound(array<int, 2>{pt, -MOD});
      assert(it != T[v].end());
      assert((*it)[0] == pt);
      ANS5[idx] = min((*it)[1] + lazy[v] + d[v], ANS5[idx]);
      cerr << "# " << v << ' ' << idx << ' ' << pt << ' ' << (*it)[1] + lazy[v] << ' ' <<  d[v] << '\n';
    }


    for(auto [idx, l, r]: Q[v]){
      auto it = T[v].lower_bound(array<int, 2>{l, -MOD});
      assert(it != T[v].end());
      assert((*it)[0] == l);
      auto it2 = T[v].lower_bound(array<int, 2>{r, -MOD});
      assert(it != T[v].end());
      assert((*it2)[0] == r);
      ANS[idx] = min(ANS[idx], (*it)[1] + lazy[v] + (*it2)[1] + lazy[v]);
    }
  }

  for(int i = 1; i <= q; ++i){
    // cout << ANS2[i] << ' ' << ANS3[i] << ' ';
    cout << min({ANS[i], ANS2[i] + ANS3[i], ANS4[i] + ANS5[i]}) - 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: 5 / 5
• Subtask 2: 0 / 15
• Subtask 3: 25 / 25
• Subtask 4: 0 / 55