#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
int n;
int sum[maxn], p[maxn], cnt[maxn];
int tree[maxn];
vector<int> temp;
set<int> act;
vector<pair<int,int> > a;
void update(int x,int val) {
x++;
while(x<=n) {
tree[x] += val;
x += x&-x;
}
}
int query(int x) {
x++;
int res = 0;
while(x>0) {
res += tree[x];
x -= x&-x;
}
return res;
}
int findpos(int x) {
int l,r,mid,res=-1;
l = 0; r = n-1;
while(l<=r) {
mid = (l+r)/2;
if(query(mid)<=x) res = mid, l = mid+1;
else r = mid-1;
}
return res;
}
int GetBestPosition(int N, int C, int X, int *K, int *L, int *R) {
int i,j,l,r;
pair<int,int> ans;
set<int>::iterator it;
n = N;
for(i=0;i<n;i++) sum[i] = sum[i-1] + ((i<n-1 && K[i]>X) ? 1 : 0);
for(i=0;i<n;i++) update(i,1), act.insert(i);
for(i=0;i<C;i++) {
l = findpos(L[i])+1; r = findpos(R[i]+1);
// printf("%d : [%d, %d]\n",i,l,r);
temp.clear();
for(it=act.find(l);it!=act.end() && *it<=r;++it) temp.push_back(*it);
for(j=0;j<temp.size();j++) update(temp[j],-1), act.erase(temp[j]);
update(l,1); act.insert(l);
if(sum[r-1]-sum[l-1]==0) cnt[l]++, cnt[r+1]--;
}
ans = {0,0};
for(i=0;i<n;i++) cnt[i] += cnt[i-1], ans = max(ans,{cnt[i],-i});
return -ans.second;
}
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<temp.size();j++) update(temp[j],-1), act.erase(temp[j]);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
3584 KB |
Output is correct |
2 |
Correct |
0 ms |
3584 KB |
Output is correct |
3 |
Correct |
0 ms |
3584 KB |
Output is correct |
4 |
Correct |
0 ms |
3584 KB |
Output is correct |
5 |
Correct |
0 ms |
3584 KB |
Output is correct |
6 |
Correct |
0 ms |
3584 KB |
Output is correct |
7 |
Correct |
0 ms |
3584 KB |
Output is correct |
8 |
Correct |
0 ms |
3584 KB |
Output is correct |
9 |
Correct |
0 ms |
3584 KB |
Output is correct |
10 |
Correct |
0 ms |
3584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
3716 KB |
Output is correct |
2 |
Correct |
3 ms |
3848 KB |
Output is correct |
3 |
Correct |
3 ms |
3848 KB |
Output is correct |
4 |
Correct |
3 ms |
3848 KB |
Output is correct |
5 |
Correct |
3 ms |
3848 KB |
Output is correct |
6 |
Correct |
3 ms |
3848 KB |
Output is correct |
7 |
Correct |
3 ms |
3848 KB |
Output is correct |
8 |
Correct |
6 ms |
3848 KB |
Output is correct |
9 |
Correct |
3 ms |
3980 KB |
Output is correct |
10 |
Correct |
6 ms |
3852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
6356 KB |
Output is correct |
2 |
Correct |
176 ms |
9480 KB |
Output is correct |
3 |
Correct |
63 ms |
9504 KB |
Output is correct |
4 |
Correct |
156 ms |
9480 KB |
Output is correct |
5 |
Correct |
159 ms |
9180 KB |
Output is correct |
6 |
Correct |
196 ms |
9216 KB |
Output is correct |
7 |
Correct |
186 ms |
9480 KB |
Output is correct |
8 |
Correct |
159 ms |
9480 KB |
Output is correct |
9 |
Correct |
63 ms |
9516 KB |
Output is correct |
10 |
Correct |
86 ms |
8728 KB |
Output is correct |