#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 time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
2 ms |
436 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
312 KB |
Output is correct |
| 8 |
Correct |
1 ms |
304 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1164 KB |
Output is correct |
| 3 |
Correct |
4 ms |
728 KB |
Output is correct |
| 4 |
Correct |
9 ms |
1056 KB |
Output is correct |
| 5 |
Correct |
8 ms |
1080 KB |
Output is correct |
| 6 |
Correct |
8 ms |
980 KB |
Output is correct |
| 7 |
Correct |
10 ms |
1212 KB |
Output is correct |
| 8 |
Correct |
9 ms |
1148 KB |
Output is correct |
| 9 |
Correct |
3 ms |
700 KB |
Output is correct |
| 10 |
Correct |
10 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
7112 KB |
Output is correct |
| 2 |
Correct |
202 ms |
19072 KB |
Output is correct |
| 3 |
Correct |
84 ms |
9532 KB |
Output is correct |
| 4 |
Correct |
194 ms |
16792 KB |
Output is correct |
| 5 |
Correct |
205 ms |
17180 KB |
Output is correct |
| 6 |
Correct |
178 ms |
13896 KB |
Output is correct |
| 7 |
Correct |
198 ms |
17052 KB |
Output is correct |
| 8 |
Correct |
200 ms |
17864 KB |
Output is correct |
| 9 |
Correct |
73 ms |
9036 KB |
Output is correct |
| 10 |
Correct |
92 ms |
9484 KB |
Output is correct |
