제출 #796503

#제출 시각아이디문제언어결과실행 시간메모리
796503esomer마상시합 토너먼트 (IOI12_tournament)C++17
100 / 100
205 ms19072 KiB
#include<bits/stdc++.h> //~ #include "tournament.h" using namespace std; struct segTree{ vector<int> sum, mn, mx; int sz, siz; void init(int n){ sz = 1; while(sz < n) sz *= 2; siz = sz; sum.assign(2 * sz, 0); mn.assign(2 * sz, 1e9); mx.assign(2 * sz, -1); } void set(int i, int val, int x, int lx, int rx){ if(rx - lx == 1){ sum[x] = val; return; } int m = (lx + rx) / 2; if(i < m) set(i, val, 2 * x + 1, lx, m); else set(i, val, 2 * x + 2, m, rx); sum[x] = sum[2 * x + 1] + sum[2 * x + 2]; } void set(int i, int val){ set(i, val, 0, 0, siz); } void set_mn(int i, int val, int x, int lx, int rx, bool obl){ if(rx - lx == 1){ if(obl == 0) mn[x] = min(val, mn[x]); else mn[x] = val; return; } int m = (lx + rx) / 2; if(i < m) set_mn(i, val, 2 * x + 1, lx, m, obl); else set_mn(i, val, 2 * x + 2, m, rx, obl); mn[x] = min(mn[2 * x + 1], mn[2 * x + 2]); } void set_mn(int i, int val, bool obl = 0){ set_mn(i, val, 0, 0, siz, obl); } void set_mx(int i, int val, int x, int lx, int rx, bool obl){ if(rx - lx == 1){ if(obl == 0) mx[x] = max(val, mx[x]); else mx[x] = val; return; } int m = (lx + rx) / 2; if(i < m) set_mx(i, val, 2 * x + 1, lx, m, obl); else set_mx(i, val, 2 * x + 2, m, rx, obl); mx[x] = max(mx[2 * x + 1], mx[2 * x + 2]); } void set_mx(int i, int val, bool obl = 0){ set_mx(i, val, 0, 0, siz, obl); } int walk(int val, int x, int lx, int rx, int curr){ if(rx - lx == 1){ //~ cout << "lx " << lx << " rx " << rx << " val " << val << " curr " << curr << " sum " << sum[x] << endl; assert(curr + sum[x] == val); return lx; } int m = (lx + rx) / 2; if(sum[2 * x + 1] + curr >= val) return walk(val, 2 * x + 1, lx, m, curr); else return walk(val, 2 * x + 2, m, rx, curr + sum[2 * x + 1]); } int walk(int val){ return walk(val, 0, 0, siz, 0); } int calc_mn(int l, int r, int x, int lx, int rx){ if(lx >= l && rx <= r){ return mn[x]; }else if(lx >= r || rx <= l) return 1e9; int m = (lx + rx) / 2; int c1 = calc_mn(l, r, 2 * x + 1, lx, m); int c2 = calc_mn(l, r, 2 * x + 2, m, rx); return min(c1, c2); } int calc_mn(int l, int r){ return calc_mn(l, r, 0, 0, siz); } int calc_mx(int l, int r, int x, int lx, int rx){ if(lx >= l && rx <= r){ return mx[x]; }else if(lx >= r || rx <= l) return -1e9; int m = (lx + rx) / 2; int c1 = calc_mx(l, r, 2 * x + 1, lx, m); int c2 = calc_mx(l, r, 2 * x + 2, m, rx); return max(c1, c2); } int calc_mx(int l, int r){ return calc_mx(l, r, 0, 0, siz); } int get_mn(int i){ return calc_mn(i, i + 1); } int get_mx(int i){ return calc_mx(i, i + 1); } }; struct segTree2{ vector<int> sums; int sz, siz; void init(int n){ sz = 1; while(sz < n) sz *= 2; siz = sz; sums.assign(2 * sz, 0); } void set(int i, int val, int x, int lx, int rx){ if(rx - lx == 1){ sums[x] = val; return; } int m = (lx + rx) / 2; if(i < m) set(i, val, 2 * x + 1, lx, m); else set(i, val, 2 * x + 2, m, rx); sums[x] = sums[2 * x + 1] + sums[2 * x + 2]; } void set(int i, int val){ set(i, val, 0, 0, siz); } int sum(int l, int r, int x, int lx, int rx){ if(lx >= l && rx <= r) return sums[x]; else if(lx >= r || rx <= l) return 0; int m = (lx + rx) / 2; int s1 = sum(l, r, 2 * x + 1, lx, m); int s2 = sum(l, r, 2 * x + 2, m, rx); return s1 + s2; } int sum(int l, int r){ return sum(l, r, 0, 0, siz); } }; int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){ vector<pair<int, int>> queries(C); segTree st; st.init(N); for(int i = 0; i < N; i++){ st.set_mn(i, i); st.set_mx(i, i); st.set(i, 1); } for(int i = 0; i < C; i++){ S[i]++; E[i]++; //~ cout << "i " << i << " s[i] " << S[i] << endl; int mn = 1e9; int mx = -1e9; int total = 0; int first = -1; while(total < E[i] - S[i] + 1){ total++; int ind = st.walk(S[i]); if(first == -1) first = ind; st.set(ind, 0); mn = min(mn, st.get_mn(ind)); mx = max(mx, st.get_mx(ind)); } st.set(first, 1); st.set_mn(first, mn); st.set_mx(first, mx); queries[i] = {mn, mx}; } for(int i = 0; i < N; i++){ st.set_mx(i, K[i], 1); } vector<vector<pair<int, int>>> start(N); vector<vector<pair<int, int>>> ends(N); for(int i = 0; i < C; i++){ start[queries[i].first].push_back({queries[i].second, i}); } segTree2 stq; stq.init(C); int mx_wins = 0; int ans = 0; set<int> bad; for(int i = 0; i < N; i++){ for(pair<int, int> p : start[i]){ ends[p.first].push_back({i, p.second}); int mx = st.calc_mx(i, p.first); if(mx < R) stq.set(p.second, 1); else bad.insert(p.second); } for(pair<int, int> p : ends[i]){ int l = p.first; int mx = st.calc_mx(l, i); if(mx < R) stq.set(p.second, 0); else bad.erase(p.second); } int hi = C; if((int)bad.size() > 0) hi = *bad.begin(); int wins = stq.sum(0, hi); if(wins > mx_wins){ mx_wins = wins; ans = i; } } return ans; } //~ int main() { //~ int tmp; //~ int N, C, R; //~ int *K, *S, *E; //~ tmp = scanf("%d %d %d", &N, &C, &R); //~ assert(tmp == 3); //~ K = (int*) malloc((N-1) * sizeof(int)); //~ S = (int*) malloc(C * sizeof(int)); //~ E = (int*) malloc(C * sizeof(int)); //~ int i; //~ for (i = 0; i < N-1; i++) { //~ tmp = scanf("%d", &K[i]); //~ assert(tmp == 1); //~ } //~ for (i = 0; i < C; i++) { //~ tmp = scanf("%d %d", &S[i], &E[i]); //~ assert(tmp == 2); //~ } //~ printf("%d\n", GetBestPosition(N, C, R, K, S, E)); //~ return 0; //~ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...