using namespace std;
#include <bits/stdc++.h>
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<bool> vb;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
int n, c, r;
vi k, s, e;
struct SegTree {
int n; vector<ll> tr;
SegTree(int N) {
n = N;
tr.assign(4*n, 0);
}
int l(int x) {return x<<1;}
int r(int x) {return (x<<1)|1;}
ll query(int x, int L, int R, int i, int j) {
if (L >= i && R <= j) return tr[x];
if (i > R || j < L) return 0;
int mid = (L + R) / 2;
return query(l(x), L, mid, i, j) + query(r(x), mid + 1, R, i, j);
}
ll query(int i, int j) {return query(1, 0, n - 1, i, j);}
void update(int x, int L, int R, int i, ll v) {
if (i > R || i < L) return;
if (L == R) {
tr[x] = v;
return;
}
int mid = (L + R) / 2;
update(l(x), L, mid, i, v);
update(r(x), mid + 1, R, i, v);
tr[x] = tr[l(x)] + tr[r(x)];
return;
}
void update(int i, ll v) {update(1, 0, n - 1, i, v);}
};
struct UF {
int n;
vi p, r;
UF(int N) {
n = N;
p.resize(n); rep(i,0,n) p[i] = i;
r.assign(n, 1);
}
int P(int x) {return (p[x] == x) ? x : p[x] = P(p[x]);}
void join(int x, int y) {
x = P(x); y = P(y);
if (x == y) return;
if (r[x] > r[y]) swap(x, y);
p[x] = y;
if (r[x] == r[y]) r[y]++;
}
bool joined(int x, int y) {
x = P(x); y = P(y);
return (x == y);
}
};
int eval(int x) {
vi nk(n);
rep(i,0,x) nk[i] = k[i];
nk[x] = 1;
rep(i,x+1,n) nk[i] = k[i - 1];
int ret = 0;
SegTree st(n);
rep(i,0,n) st.update(i,nk[i]);
rep(i,0,n) {
if (s[i] > x || e[i] < x) continue;
if (st.query(s[i], e[i]) == 1) ret++;
else return ret;
}
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n = N; c = C; r = R;
k.resize(n-1); rep(i,0,n-1) k[i] = (K[i] > r) ? 2 : 0;
s.resize(c); e.resize(c);
rep(i,0,c) {s[i] = S[i]; e[i] = E[i];}
SegTree compact(n);
rep(i,0,n) compact.update(i,0);
rep(i,0,c) {
// binary search start
int low = 0, high = s[i] + 1, mid;
while (high - low > 1) {
mid = (low + high) / 2;
if (mid - compact.query(0, mid) <= s[i]) low = mid;
else high = mid;
}
s[i] = low;
low = s[i]; high = n;
while (high - low > 1) {
mid = (low + high) / 2;
if (mid - compact.query(s[i], mid) - s[i] <= (e[i] - s[i])) low = mid;
else high = mid;
}
ll currentsi = compact.query(s[i], s[i]);
ll newsi = currentsi + (e[i] - s[i]);
e[i] = low;
compact.update(s[i], newsi);
}
int ans = 0, res = 0;
rep(i,0,n) {
int nres = eval(i);
if (nres > res) {
res = nres;
ans = i;
}
}
return ans;
}
// int main() {
// int n = 5, c = 2, r = 3;
// int k[] = {0, 1, 2, 4};
// int s[] = {1, 0};
// int e[] = {3, 2};
// GetBestPosition(n, c, r, k, s, e);
// }
Compilation message
tournament.cpp: In function 'int eval(int)':
tournament.cpp:78:10: warning: control reaches end of non-void function [-Wreturn-type]
78 | vi nk(n);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1067 ms |
5048 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
