#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], id[4 * maxn], val[4 * maxn], tree[4 * maxn];
// ID
void upd(int u,int st, int en, int l,int r,int val) {
if(l > en || r < st) return;
if(st <= l && r <= en) {
id[u] += val;
return;
}
int mid = (l + r) / 2;
upd(2 * u, st, en, l, mid, val);
upd(2 * u + 1, st, en, mid + 1, r, val);
}
int get(int u,int idx, int l, int r) {
if(l > idx || r < idx) return 0;
if(l == r) return id[u];
int mid = (l + r) / 2;
return id[u] + get(2 * u, idx, l, mid) + get(2 * u + 1, idx, mid + 1, r);
}
/// MAX ELEMENT ON A SEGMENT
void build(int u,int l, int r) {
if(l == r) {
tree[u] = a[l];
return;
}
int mid = (l + r) / 2;
build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
tree[u] = max(tree[2 * u], tree[2 * u + 1]);
}
int mx(int u,int st,int en, int l,int r) {
if(l > en || r < st) return 0;
if(st <= l && r <= en) return tree[u];
int mid = (l + r) / 2;
return max(mx(2 * u, st, en, l, mid), mx(2 * u + 1, st ,en ,mid + 1, r));
}
void upd(int u,int st, int en, int l, int r) {
if(l > en || r < st) return;
if(st <= l && r <= en) {
val[u] ++;
return;
}
int mid = (l + r) / 2;
upd(2 * u, st, en ,l, mid); upd(2 * u + 1, st, en ,mid + 1, r);
}
int get_mx(int u,int id, int l,int r) {
if(l > id || r < id) return 0;
if(l == r) return val[u];
int mid = (l + r) / 2;
return val[u] + get_mx(2 * u, id, l, mid) + get_mx(2 * u + 1,id, mid + 1, r);
}
int GetBestPosition(int n, int C, int R, int *K, int *s, int *e) {
set<int> ok;
for(int i = 0; i < n - 1; i++) a[i] = K[i];
for(int i = 1; i < n ;i++) {
upd(1, i, n - 1, 0, n - 1, 1);
ok.insert(i);
}
build(1, 0, n - 2);
pair<int,int> ans; ans = {0, 0};
for(int i = 0; i < C; i++) {
int l = get(1, s[i], 0, n - 1), r = get(1, e[i], 0, n - 1);
upd(1, s[i] + 1, n - 1, 0, n - 1, get(1, e[i] + 1, 0, n - 1) - get(1, s[i] + 1, 0, n - 1));
if(mx(1, l, r - 1, 0, n - 2) > R) {
while(ok.upper_bound(l - 1) != ok.end() && *ok.upper_bound(l - 1) < r) {
int id = *ok.upper_bound(l - 1);
ans = max(ans, {get_mx(1, id, 0, n - 1), -id});
ok.erase(*ok.upper_bound(l - 1));
}
} else upd(1, l, r, 0, n - 1);
}
while(ok.upper_bound(0 - 1) != ok.end()) {
int id = *ok.upper_bound(0 - 1);
ans = max(ans, {get_mx(1, id, 0, n - 1), -id});
ok.erase(*ok.upper_bound(0 - 1));
}
return -ans.second;
}
/*
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);
int main() {
int tmp;
/* Set input and output buffering
char *inbuf, *outbuf;
inbuf = (char*) malloc(inbuf_len * sizeof(char));
outbuf = (char*) malloc(outbuf_len * sizeof(char));
tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
assert(tmp == 0);
tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
assert(tmp == 0);
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;
}*/
Compilation message
tournament.cpp:98:3: warning: "/*" within comment [-Wcomment]
98 | /* Set input and output buffering
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
5444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
