#define pii pair<int,int>
#define f first
#include<bits/stdc++.h>
#define s second
using namespace std;
const int nn = 2e5 + 5;
int t[4 * nn], n;
void upd(int u,int ind, int l,int r,int v) {
if(l > ind || r < ind) return;
if(l == r) {
t[u] = v;
return;
}
int mid = (l + r) / 2;
upd(2 * u, ind, l, mid, v); upd(2 * u + 1, ind, mid + 1, r, v);
t[u] = t[2 * u] + t[2 * u + 1];
}
int kth(int u,int k,int l,int r) {
if(l == r) return l;
int mid = (l + r) / 2;
if(t[2 * u] >= k) return kth(2 * u, k, l, mid);
return kth(2 * u + 1, k - t[2 * u], mid + 1, r);
}
//
void add(int id, int v) {
id++;
for(id; id <= n; id += id & (-id)) t[id] += v;
}
int get(int id) {
id++;
int ans = 0;
for(id; id >= 1; id -= id & (-id)) ans += t[id];
return ans;
}
int GetBestPosition(int N, int c, int r, int *k, int *ss, int *e) {
vector<pii> qry;
n = N;
for(int i = 1; i <= n + 1; i++) upd(1, i, 1, n + 1, 1);
for(int i = 0; i < c; i++) {
ss[i]++; e[i]++;
int l = kth(1, ss[i], 1, n + 1), r = kth(1, e[i] + 1, 1, n + 1) - 1;
while(true) {
int pos = kth(1, ss[i] + 1, 1, n + 1);
if(pos > r) break;
upd(1, pos, 1, n + 1, 0);
}
qry.push_back({l, r});
}
for(int i = 1; i <= n; i++) t[i] = 0;
set<int> b;
for(int i = 0; i < n; i++) {
if(k[i] > r) b.insert(i + 1);
}
set<int> s; for(int i = 0; i < n; i++) s.insert(i);
pii ans; ans = {0, 0};
for(int i = 0; i < qry.size(); i++) {
int l = qry[i].f, r = qry[i].s;
if(b.upper_bound(l - 1) != b.end() && *b.upper_bound(l - 1) < r) {
while(s.upper_bound(l - 2) != s.end() && *s.upper_bound(l - 2) <= r - 1) {
int x = *s.upper_bound(l - 2);
s.erase(x);
ans = max(ans, {get(x), -x});
}
}
else add(l - 1, 1), add(r, -1);
}
while(s.upper_bound(-1) != s.end()) {
int x = *s.upper_bound(-1);
s.erase(x);
ans = max(ans, {get(x), -x});
}
return -ans.s;
}
/*
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
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:87:3: warning: "/*" within comment [-Wcomment]
87 | /* Set input and output buffering
|
tournament.cpp: In function 'void add(int, int)':
tournament.cpp:28:6: warning: statement has no effect [-Wunused-value]
28 | for(id; id <= n; id += id & (-id)) t[id] += v;
| ^~
tournament.cpp: In function 'int get(int)':
tournament.cpp:33:6: warning: statement has no effect [-Wunused-value]
33 | for(id; id >= 1; id -= id & (-id)) ans += t[id];
| ^~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0; i < qry.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
316 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
308 KB |
Output is correct |
| 10 |
Correct |
1 ms |
308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
7 ms |
980 KB |
Output is correct |
| 3 |
Correct |
4 ms |
552 KB |
Output is correct |
| 4 |
Correct |
7 ms |
852 KB |
Output is correct |
| 5 |
Correct |
8 ms |
776 KB |
Output is correct |
| 6 |
Correct |
6 ms |
724 KB |
Output is correct |
| 7 |
Correct |
7 ms |
852 KB |
Output is correct |
| 8 |
Correct |
7 ms |
852 KB |
Output is correct |
| 9 |
Correct |
4 ms |
724 KB |
Output is correct |
| 10 |
Correct |
9 ms |
772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
5024 KB |
Output is correct |
| 2 |
Correct |
149 ms |
12828 KB |
Output is correct |
| 3 |
Correct |
89 ms |
7208 KB |
Output is correct |
| 4 |
Correct |
174 ms |
12376 KB |
Output is correct |
| 5 |
Correct |
142 ms |
11564 KB |
Output is correct |
| 6 |
Correct |
122 ms |
8644 KB |
Output is correct |
| 7 |
Correct |
150 ms |
11948 KB |
Output is correct |
| 8 |
Correct |
173 ms |
12608 KB |
Output is correct |
| 9 |
Correct |
94 ms |
11084 KB |
Output is correct |
| 10 |
Correct |
105 ms |
9248 KB |
Output is correct |
