Submission #1263955

#TimeUsernameProblemLanguageResultExecution timeMemory
1263955Bui_Quoc_CuongJousting tournament (IOI12_tournament)C++20
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; int n, q, s; int a[MAXN], L[MAXN], R[MAXN]; int far[MAXN], Left[MAXN], Right[MAXN]; int st[4 * MAXN]; void build(int id, int l, int r){ if(l == r){ st[id] = 1; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); st[id] = st[id << 1] + st[id << 1 | 1]; } void update(int pos, int val){ int id = 1, l = 1, r = n; while(l < r){ int mid = (l + r) >> 1; if(pos <= mid) id = id << 1, r = mid; else id = id << 1 | 1, l = mid + 1; } st[id] = val; while(id > 1){ id >>= 1; st[id] = st[id << 1] + st[id << 1 | 1]; } } int walk(int val){ int id = 1, l = 1, r = n; while(1){ if(l == r) return l; int mid = (l + r) >> 1; if(st[id << 1] < val){ val-= st[id << 1]; l = mid + 1; id = id << 1 | 1; } else{ r = mid; id = id << 1; } } return l; } int rmq[MAXN][20]; void work(){ for(int i = 1; i <= n - 1; i++) rmq[i][0] = a[i]; for(int j = 1; (1 << j) <= n; j++){ for(int i = 1; i + (1 << (j)) - 1 <= n; i++){ rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]); } } } int get(int l, int r){ int k = __lg(r - l + 1); return max(rmq[l][k], rmq[r - (1 << k) + 1][k]); } int f[MAXN]; int GetBestPosition(int n, int q, int k, int *K, int *Le, int *Ri){ s = k; for(int i = 1; i < n; i++) a[i] = K[i - 1]; for(int i = 1; i <= q; i++){ L[i] = Le[i - 1]; R[i] = Ri[i - 1]; L[i]++; R[i]++; } for(int i = 1; i <= n; i++) far[i] = i; build(1, 1, n); work(); for(int i = 1; i <= q; i++){ int l = L[i], r = R[i]; int p = walk(l); for(int j = 1; j <= r - l; j++){ int nxt = walk(L[i] + 1); far[p] = far[nxt]; update(nxt, 0); } Left[i] = p; Right[i] = far[p]; } for(int i = 1; i <= q; i++){ if(s > get(Left[i], Right[i] - 1)){ f[Left[i]]++; f[Right[i]]--; } } for(int i = 1; i <= n; i++) f[i] = f[i - 1] + f[i]; return max_element(f + 1, f + 1 + n) - f - 1; } //int main(){ // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // #define taskname "kieuoanh" // if(fopen(taskname".inp", "r")){ // freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); // } // cin >> n >> q >> s; // for(int i = 1; i <= n - 1; i++){ // cin >> a[i]; // } // for(int i = 1; i <= q; i++){ // cin >> L[i] >> R[i]; // L[i]++; R[i]++; // } // for(int i = 1; i <= n; i++) far[i] = i; // build(1, 1, n); // work(); // // for(int i = 1; i <= q; i++){ // int l = L[i], r = R[i]; // int p = walk(l); // for(int j = 1; j <= r - l; j++){ // int nxt = walk(L[i] + 1); // far[p] = far[nxt]; // update(nxt, 0); // } // Left[i] = p; // Right[i] = far[p]; // } // // for(int i = 1; i <= q; i++){ // if(s > get(Left[i], Right[i] - 1)){ // f[Left[i]]++; // f[Right[i]]--; // } // } // for(int i = 1; i <= n; i++) f[i] = f[i - 1] + f[i]; // // cout << max_element(f + 1, f + 1 + n) - f - 1; // // return 0; //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...