#include<bits/stdc++.h>
using namespace std;
#define maxn 10005
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]--;
a.push_back({l,r});
}
}
ans = {0,0};
for(i=0;i<n;i++) {
int ok = 0;
for(int j=0;j<a.size();j++) if(a[j].first<=i && a[j].second>=i) ok++;
ans = max(ans,{ok,-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]);
^
tournament.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<a.size();j++) if(a[j].first<=i && a[j].second>=i) ok++;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2180 KB |
Output is correct |
2 |
Correct |
0 ms |
2180 KB |
Output is correct |
3 |
Correct |
0 ms |
2180 KB |
Output is correct |
4 |
Correct |
0 ms |
2180 KB |
Output is correct |
5 |
Correct |
0 ms |
2180 KB |
Output is correct |
6 |
Correct |
0 ms |
2180 KB |
Output is correct |
7 |
Correct |
0 ms |
2180 KB |
Output is correct |
8 |
Correct |
0 ms |
2180 KB |
Output is correct |
9 |
Correct |
0 ms |
2180 KB |
Output is correct |
10 |
Correct |
0 ms |
2180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
2312 KB |
Output is correct |
2 |
Correct |
13 ms |
2444 KB |
Output is correct |
3 |
Correct |
3 ms |
2444 KB |
Output is correct |
4 |
Correct |
16 ms |
2444 KB |
Output is correct |
5 |
Correct |
13 ms |
2444 KB |
Output is correct |
6 |
Correct |
39 ms |
2600 KB |
Output is correct |
7 |
Correct |
16 ms |
2444 KB |
Output is correct |
8 |
Correct |
13 ms |
2444 KB |
Output is correct |
9 |
Correct |
0 ms |
2576 KB |
Output is correct |
10 |
Correct |
19 ms |
2580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
13 ms |
2576 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |