Submission #830182

#TimeUsernameProblemLanguageResultExecution timeMemory
830182LiudasJousting tournament (IOI12_tournament)C++17
0 / 100
33 ms1876 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); for(int i = 0; i < N-1; i ++){ tree.add_val(i, K[i]); tree.add_alive(i, 1); } tree.add_alive(N-1, 1); tree.add_alive(N, 1); vector<int> pref(N + 5); for(int i = 0; i < C; i ++){ int s = tree.get_alive(S[i] + 1), e = tree.get_alive(E[i] + 1); //cout << S[i] << " " << s << " " << E[i] << " " << e << endl << endl << endl; if(tree.get_val(s, e) < R){ pref[s] ++; pref[e + 1]--; } for(int j = S[i]; j < E[i]; j ++){ tree.add_alive(tree.get_alive(S[i] + 1), 0); } } int ans = 0; int id = 0; int p = 0; for(int i = 0; i < N; i ++){ p += pref[i]; //cout << p << " "; if(ans < p){ ans = p; id = i; } } return id; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...