Submission #830195

#TimeUsernameProblemLanguageResultExecution timeMemory
830195LiudasJousting tournament (IOI12_tournament)C++17
17 / 100
35 ms2168 KiB
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <vector> #include <algorithm> #include <iostream> //#include "tournament.h" using namespace std; class segment_tree{ public: vector<int> tree, alive; int N; segment_tree(int K){ N = 1; while(N <= K){ N *= 2; } tree.assign(N * 2, 0); alive.assign(N * 2, 0); } void add_alive(int head, int l, int r, int pos, int val){ if(r - l == 1){ alive[head] = val; return; } int mid = (l + r) / 2; if(pos < mid){ add_alive(head * 2 + 1, l, mid, pos, val); } else{ add_alive(head * 2 + 2, mid, r, pos, val); } alive[head] = alive[head * 2 + 1] + alive[head * 2 + 2]; } void add_alive(int pos, int val){ add_alive(0, 0, N, pos, val); } int get_alive(int head, int l, int r, int need, int left){ //cout << l << " " << r << " " << need << " " << alive[head] + left << endl; if(r - l == 1){ return l; } int mid = (l + r) / 2; if(need <= alive[head * 2 + 1] + left){ return get_alive(head * 2 + 1, l, mid, need, left); } else{ return get_alive(head * 2 + 2, mid, r, need, left + alive[head * 2 + 1]); } } int get_alive(int need){ return get_alive(0, 0, N, need, 0); } void add_val(int head, int l, int r, int pos, int val){ if(r - l == 1){ tree[head] = val; return; } int mid = (l + r) / 2; if(pos < mid){ add_val(head * 2 + 1, l, mid, pos, val); } else{ add_val(head * 2 + 2, mid, r, pos, val); } tree[head] = max(tree[head * 2 + 1], tree[head * 2 + 2]); } void add_val(int pos, int val){ add_val(0, 0, N, pos, val); } int get_val(int head, int l, int r, int L, int R){ if(L <= l && R >= r){ return tree[head]; } if(L >= r || R <= l){ return 0; } int mid = (l + r) / 2; return max(get_val(head * 2 + 1, l, mid, L, R), get_val(head * 2 + 2, mid, r, L, R)); } int get_val(int l, int r){ return get_val(0, 0, N, l, r); } }; int GetBestPosition(int N, int C, int R, int K[], int S[], int E[]){ segment_tree tree(N); vector<int> pref(N + 5); int ans = 0; int id = 0; vector<int> arr(N-1); for(int i = 0; i < N-1; i ++){ arr[i] = K[i]; } for(int j = 0; j < N-1; j ++){ tree.add_val(j, arr[j]); tree.add_alive(j, 1); } tree.add_alive(N-1, 1); tree.add_alive(N, 1); for(int j = 0; j < C; j ++){ int s = tree.get_alive(S[j] + 1), e = tree.get_alive(E[j] + 2); //cout << s << " " << e << " " << tree.get_val(s, e)<< endl; if(tree.get_val(s, e-1) < R){ pref[s] ++; pref[e + 1]--; } for(int k = S[j]; k < E[j]; k ++){ tree.add_alive(tree.get_alive(S[j] + 2), 0); } } int p = 0; for(int j = 0; j < N; j ++){ p += pref[j]; //cout << p << " "; if(ans < p){ ans = p; id = j; } } //cout << endl; return id; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...