제출 #1210136

#제출 시각아이디문제언어결과실행 시간메모리
1210136mychecksedadRailway Trip (JOI17_railway_trip)C++20
100 / 100
105 ms47304 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 = 1e6+100, M = 1e5+10, K = 22, 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], L[N][K], R[N][K]; vector<int> g[N]; 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); } vector<pii> Q; for(int i = 1; i <= n; ++i){ L[i][0] = i; while(Q.size() && Q.back().ff < a[i]) Q.pop_back(); if(Q.size()){ L[i][0] = Q.back().ss; } Q.pb({a[i], i}); } Q.clear(); for(int i = n; i >= 1; --i){ R[i][0] = i; while(Q.size() && Q.back().ff < a[i]) Q.pop_back(); if(Q.size()){ R[i][0] = Q.back().ss; } Q.pb({a[i], i}); } for(int j = 1; j < K; ++j){ for(int i = 1; i <= n; ++i){ L[i][j] = min(L[L[i][j - 1]][j - 1], L[R[i][j - 1]][j - 1]); R[i][j] = max(R[R[i][j - 1]][j - 1], R[L[i][j - 1]][j - 1]); } } for(int i = 1; i <= q; ++i){ int x, y; cin >> x >> y; if(y < x) swap(y, x); int l = x, r = x; int ans = 0; for(int j = K-1; j >= 0; --j){ if(max(R[r][j], R[l][j]) < y){ tie(l, r) = pii{min(L[l][j], L[r][j]), max(R[l][j], R[r][j])}; ans += 1<<j; } } int c = r; l = r = y; for(int j = K-1; j >= 0; --j){ if(min(L[r][j], L[l][j]) > c){ tie(l, r) = pii{min(L[l][j], L[r][j]), max(R[l][j], R[r][j])}; ans += 1<<j; } } cout << ans << '\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...