#include <algorithm>
#include <stdio.h>
#include <stack>
#define N 100001
#define NN 131072
#define INF 999999999
using namespace std;
typedef pair<pair<int,int>,int> ppi;
int n, m, knight, p[N];
int nn, tree[NN*2], tree2[NN*2], tree_max[NN*2];
pair<int,int> match[N];
ppi d[N];
stack<pair<int,int> > S;
bool cmp(ppi x, ppi y){
if(x.first.first!=y.first.first) return x.first.first<y.first.first;
return x.first.second>y.first.second;
}
int max2(int x, int y){ return x>y?x:y; }
int get_w(int lev, int l, int r, int num){
int mid=(l+r)/2;
if(l==r && num==tree[lev]) return l;
if(l==r) return 0;
if(num>tree2[lev*2]) return get_w(lev*2+1,mid+1,r,num-tree[lev*2]);
else return get_w(lev*2,l,mid,num);
}
void Update(int x){
tree[x]=tree[x*2]+tree[x*2+1];
tree2[x]=max2(tree2[x*2],tree[x*2]+tree2[x*2+1]);
if(x>1) Update(x/2);
}
int f(int lev, int l, int r, int x, int y){
int mid=(l+r)/2;
if(x<=l && r<=y) return tree_max[lev];
if(r<x || y<l) return 0;
return max2(f(lev*2,l,mid,x,y),f(lev*2+1,mid+1,r,x,y));
}
int GetBestPosition(int _n, int _m, int _knight, int *_p, int *_in1, int *_in2){
n=_n, m=_m, knight=_knight;
for(int i=0; i<n-1; i++) p[i+1]=_p[i];
for(int i=0; i<m; i++) match[i+1]=make_pair(_in1[i]+1,_in2[i]+1);
for(nn=1; nn<n; nn*=2);
for(int i=1; i<=n; i++){
tree2[i+nn-1]=tree[i+nn-1]=1;
tree_max[i+nn-1]=p[i];
}
for(int i=nn-1; i>=1; i--){
tree2[i]=tree[i]=tree[i*2]+tree[i*2+1];
tree_max[i]=max2(tree_max[i*2],tree_max[i*2+1]);
}
for(int i=1; i<=m; i++){
if(match[i].first==1) d[i].first.first=1;
else d[i].first.first=get_w(1,1,nn,match[i].first-1)+1;
d[i].first.second=get_w(1,1,nn,match[i].second);
d[i].second=i;
tree[d[i].first.first+nn-1]-=match[i].second-match[i].first;
tree2[d[i].first.first+nn-1]-=match[i].second-match[i].first;
Update((d[i].first.first+nn-1)/2);
} sort(d+1,d+m+1,cmp);
int MAX=-1, out, w=1, temp;
S.push(make_pair(INF,0));
for(int i=1; i<=n; i++){
while(S.top().first<i) S.pop();
while(w<=m && d[w].first.first<=i){
temp=f(1,1,nn,d[w].first.first,d[w].first.second-1);
if(temp<knight) S.push(make_pair(d[w].first.second,S.top().second+1));
else S.push(make_pair(d[w].first.second,0));
w++;
}
if(MAX<S.top().second) MAX=S.top().second, out=i;
} return out-1;
}
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:81:18: warning: 'out' may be used uninitialized in this function [-Wmaybe-uninitialized]
} return out-1;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
7352 KB |
Output is correct |
2 |
Correct |
0 ms |
7352 KB |
Output is correct |
3 |
Correct |
0 ms |
7352 KB |
Output is correct |
4 |
Correct |
0 ms |
7352 KB |
Output is correct |
5 |
Correct |
0 ms |
7352 KB |
Output is correct |
6 |
Correct |
0 ms |
7352 KB |
Output is correct |
7 |
Correct |
0 ms |
7352 KB |
Output is correct |
8 |
Correct |
0 ms |
7352 KB |
Output is correct |
9 |
Correct |
0 ms |
7352 KB |
Output is correct |
10 |
Correct |
0 ms |
7352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
7352 KB |
Output is correct |
2 |
Correct |
3 ms |
7484 KB |
Output is correct |
3 |
Correct |
0 ms |
7352 KB |
Output is correct |
4 |
Correct |
3 ms |
7484 KB |
Output is correct |
5 |
Correct |
3 ms |
7484 KB |
Output is correct |
6 |
Correct |
3 ms |
7352 KB |
Output is correct |
7 |
Correct |
3 ms |
7484 KB |
Output is correct |
8 |
Correct |
3 ms |
7484 KB |
Output is correct |
9 |
Correct |
0 ms |
7352 KB |
Output is correct |
10 |
Correct |
3 ms |
7488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
7752 KB |
Output is correct |
2 |
Correct |
89 ms |
9288 KB |
Output is correct |
3 |
Correct |
23 ms |
7744 KB |
Output is correct |
4 |
Correct |
89 ms |
8760 KB |
Output is correct |
5 |
Correct |
99 ms |
8988 KB |
Output is correct |
6 |
Correct |
73 ms |
8232 KB |
Output is correct |
7 |
Correct |
93 ms |
8892 KB |
Output is correct |
8 |
Correct |
103 ms |
8940 KB |
Output is correct |
9 |
Correct |
13 ms |
7744 KB |
Output is correct |
10 |
Correct |
16 ms |
7744 KB |
Output is correct |