#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
int n;
int sum[maxn], p[maxn], cnt[maxn];
int L[maxn], R[maxn];
int tree[maxn];
vector<int> temp;
set<int> act;
void update(int x,int val) {
while(x<=n) {
tree[x] += val;
x += x&-x;
}
}
int query(int x) {
int res = 0;
while(x>0) {
res += tree[x];
x -= x&-x;
}
return res;
}
int findpos(int x) {
int l,r,mid,res=0;
l = 1; r = n;
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 *S, int *E) {
int i,j,l,r,ans;
set<int>::iterator it;
n = N;
for(i=1;i<=n;i++) sum[i] = sum[i-1] + (K[i-1]>X);
for(i=0;i<C;i++) L[i] = S[i]+1, R[i] = E[i]+1;
for(i=1;i<=n;i++) update(i,1), act.insert(i);
for(i=0;i<C;i++) {
l = findpos(L[i]-1)+1; r = findpos(R[i]);
// printf("%d : [%d, %d]\n",i,l,r);
temp.clear();
for(it=act.lower_bound(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;
for(i=1;i<=n;i++) {
cnt[i] += cnt[i-1];
ans = max(ans,cnt[i]);
}
return ans;
}
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:50: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 |
2256 KB |
Output is correct |
2 |
Incorrect |
0 ms |
2256 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
2388 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
13 ms |
2652 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |