#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
using namespace std;
const int Nmax = 1e5 + 5;
typedef pair<int,int> Pair;
int a[Nmax], n, C, start[Nmax], finish[Nmax], prv[Nmax], nxt[Nmax];
class AIB
{
int a[Nmax];
int ub(int x) { return (x&(-x)); }
public:
void upd(int pos, int add)
{
++pos;
for(; pos<=n; pos+=ub(pos)) a[pos] += add;
}
int query(int pos)
{
int ans = 0;
for(; pos; pos-=ub(pos)) ans += a[pos];
return ans;
}
int find_kth(int pos)
{
int st, dr;
st = 1; dr = n;
while(st <= dr)
if(query(mid) < pos) st = mid+1;
else dr = mid-1;
return st - 1;
}
} aib;
void precalc()
{
int i;
set<int> S;
for(i=0; i<n; ++i)
{
S.insert(i);
aib.upd(i, 1);
}
for(i=0; i<C; ++i)
{
int x, y;
x = aib.find_kth(start[i] + 1);
y = aib.find_kth(finish[i] + 2);
start[i] = x; finish[i] = y - 1;
set<int> :: iterator it, it2;
it = it2 = S.upper_bound(x);
while(it2 != S.end() && *it2 <= finish[i])
{
aib.upd(*it2, -1);
++it2;
}
S.erase(it, it2);
}
}
bool cmp(Pair a, Pair b)
{
return a.second - a.first < b.second - b.first;
}
class SegmentTree
{
vector<Pair> v[Nmax<<2];
int find_biggest(vector<Pair> &v, int L, int R)
{
int st, dr;
st = 0; dr = v.size() - 1;
while(st <= dr)
if(v[mid].first >= L && v[mid].second <= R) st = mid+1;
else dr = mid-1;
return st;
}
public:
void build(int node, int st, int dr)
{
sort(v[node].begin(), v[node].end(), cmp);
if(st == dr) return;
build(left_son, st, mid); build(right_son, mid+1, dr);
}
void add(int node, int st, int dr, int L, int R)
{
if(L <= st && dr <= R)
{
v[node].push_back({L, R});
return;
}
if(L <= mid) add(left_son, st, mid, L, R);
if(mid < R) add(right_son, mid+1, dr, L, R);
}
int query(int node, int st, int dr, int pos, int L, int R)
{
int ans = find_biggest(v[node], L, R);
if(st == dr) return ans;
if(pos <= mid) ans += query(left_son, st, mid, pos, L, R);
else ans += query(right_son, mid+1, dr, pos, L, R);
return ans;
}
} aint;
void init()
{
int i;
for(i=0; i<n-1; ++i)
if(!i) prv[i] = (a[i] == 1 ? i : -1);
else prv[i] = (a[i] == 1 ? i : prv[i-1]);
for(i=n-2; i>=0; --i)
if(i == n-2) nxt[i] = (a[i] == 1 ? i : n-1);
else nxt[i] = (a[i] == 1 ? i : nxt[i+1]);
for(i=0; i<C; ++i)
aint.add(1, 0, n-1, start[i], finish[i]);
aint.build(1, 0, n-1);
}
int Query(int L, int R, int pos)
{
return aint.query(1, 0, n-1, pos, L, R);
}
int GetBestPosition(int N, int _C, int R, int *K, int *S, int *E)
{
int i, bestpos; n = N;
C = _C;
for(i=0; i<n-1; ++i) a[i] = (K[i] > R);
for(i=0; i<C; ++i) start[i] = S[i], finish[i] = E[i];
precalc();
init();
int ans = -1;
for(i=-1; i<n-1; ++i) /// intre i si i+1
{
int L, R;
if(i == -1) L = 0;
else L = prv[i] + 1;
if(i == n-2) R = n-1;
else R = nxt[i+1] - 1;
++R;
int curr = Query(L, R, i+1);
if(curr > ans) ans = curr, bestpos = i;
// cerr << i << ' ' << curr << '\n';
}
return bestpos + 1;
}
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:178:22: warning: 'bestpos' may be used uninitialized in this function [-Wmaybe-uninitialized]
return bestpos + 1;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
15 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
12 ms |
9728 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9856 KB |
Output is correct |
| 5 |
Correct |
11 ms |
9728 KB |
Output is correct |
| 6 |
Correct |
11 ms |
9856 KB |
Output is correct |
| 7 |
Correct |
12 ms |
9856 KB |
Output is correct |
| 8 |
Correct |
12 ms |
9856 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9856 KB |
Output is correct |
| 10 |
Correct |
13 ms |
9856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9856 KB |
Output is correct |
| 2 |
Correct |
20 ms |
10624 KB |
Output is correct |
| 3 |
Correct |
13 ms |
10112 KB |
Output is correct |
| 4 |
Correct |
18 ms |
10496 KB |
Output is correct |
| 5 |
Correct |
20 ms |
10496 KB |
Output is correct |
| 6 |
Correct |
19 ms |
10240 KB |
Output is correct |
| 7 |
Correct |
21 ms |
10488 KB |
Output is correct |
| 8 |
Correct |
18 ms |
10496 KB |
Output is correct |
| 9 |
Correct |
13 ms |
10112 KB |
Output is correct |
| 10 |
Correct |
20 ms |
10240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
13768 KB |
Output is correct |
| 2 |
Correct |
296 ms |
30304 KB |
Output is correct |
| 3 |
Correct |
81 ms |
17144 KB |
Output is correct |
| 4 |
Correct |
223 ms |
28276 KB |
Output is correct |
| 5 |
Correct |
235 ms |
28916 KB |
Output is correct |
| 6 |
Correct |
248 ms |
18936 KB |
Output is correct |
| 7 |
Correct |
263 ms |
29104 KB |
Output is correct |
| 8 |
Correct |
228 ms |
29556 KB |
Output is correct |
| 9 |
Correct |
86 ms |
17144 KB |
Output is correct |
| 10 |
Correct |
102 ms |
17252 KB |
Output is correct |
