제출 #1210049

#제출 시각아이디문제언어결과실행 시간메모리
1210049mychecksedadRailway Trip (JOI17_railway_trip)C++20
25 / 100
313 ms128640 KiB
/* 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 maxc(int x, int y){ return a[x] >= a[y] ? x : y; } int get(int l, int r){ int k = __lg(r-l+1); return maxc(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] = 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]); } } 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; int level = get(l, r); for(auto [v, wv]: A[l][a[level]]){ for(auto [u, wu]: A[r][a[level]]){ // cerr << wv << ' ' << wu << ' ' << level << ' ' << u << ' ' << v << '\n'; ans = min(ans, wv + wu + d[max(u, v)] - d[min(u, v)]); } } for(auto [node, W]: g[level]){ for(auto [v, wv]: A[l][a[node]]){ for(auto [u, wu]: A[r][a[node]]){ // 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...