#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn=1e5+10;
const ll mod =1e9+7;
const ll base=4e18;
ll st[4*maxn];
ll la[4*maxn];
void dosth(ll id,ll left,ll right)
{
if (left==right||la[id]==0) return ;
la[id*2]=1;
st[id*2]=0;
la[id*2+1]=1;
st[id*2+1]=0;
la[id]=0;
}
void update(ll id,ll left,ll right,ll x,ll y)
{
dosth(id,left,right);
if (x>right||y<left) return;
if (x<=left&&y>=right)
{
st[id]=0;
la[id]=1;
dosth(id,left,right);
return ;
}
ll mid=(left+right)/2;
update(id*2,left,mid,x,y);
update(id*2+1,mid+1,right,x,y);
st[id]=st[id*2]+st[id*2+1];
}
void update1(ll id,ll left,ll right,ll x,ll diff)
{
dosth(id,left,right);
if (x>right||x<left) return ;
if (left==right)
{
st[id]+=diff;
return ;
}
ll mid=(left+right)/2;
update1(id*2,left,mid,x,diff);
update1(id*2+1,mid+1,right,x,diff);
st[id]=st[id*2]+st[id*2+1];
}
ll get(ll id,ll left,ll right,ll x,ll y)
{
dosth(id,left,right);
if (x>right||y<left) return 0;
if (x<=left&&y>=right) return st[id];
ll mid=(left+right)/2;
return get(id*2,left,mid,x,y)+get(id*2+1,mid+1,right,x,y);
}
/*ll st1[4*maxn];
ll la1[4*maxn];
void dosth1(ll id,ll left,ll right)
{
if (left==right||la1[id]==0) return ;
la1[id*2]+=la1[id];
st1[id*2]+=la1[id];
la1[id*2+1]+=la1[id];
st1[id*2+1]+=la1[id];
la1[id]=0;
}
void update2(ll id,ll left,ll right,ll x,ll y)
{
dosth1(id,left,right);
if (x>right||y<left) return;
if (x<=left&&y>=right)
{
st1[id]++;
la1[id]++;
dosth1(id,left,right);
return ;
}
ll mid=(left+right)/2;
update2(id*2,left,mid,x,y);
update2(id*2+1,mid+1,right,x,y);
}
ll get1(ll id,ll left,ll right,ll x)
{
dosth1(id,left,right);
if (x>right||x<left) return 0;
if (left==right) return st1[id];
ll mid=(left+right)/2;
return get1(id*2,left,mid,x)+get1(id*2+1,mid+1,right,x);
}*/
ll l[maxn];
ll r[maxn];
ll n;
ll f[maxn];
ll f1[maxn];
ll find_pos(ll x)
{
ll l=0,h= n;
while (l<=h)
{
ll mid=(l+h)/2;
if (get(1,1,n,1,mid)>=x*2) h=mid-1;
else l=mid+1;
}
return l;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
n=N;
for (int i=1;i<=n;i++)
{
update1(1,1,n,i,2);
if (i<n) f[i]=f[i-1]+(K[i-1]>R);
// cout <<f[i]<<" ";
}
//cout <<endl;
for (int i=0;i<C;i++)
{
S[i]++;
E[i]++;
l[i+1]=find_pos(S[i]-1)+1;
r[i+1]=find_pos(E[i]);
/*cout <<S[i]<<" "<<E[i]<<" "<<l[i+1]<<" "<<r[i+1]<<endl;
for (int i=1;i<=n;i++) cout <<get(1,1,n,i,i)<<" ";
cout <<endl;*/
update(1,1,n,l[i+1],r[i+1]);
/* cout <<l[i+1]<<" "<<r[i+1]<<endl;
for (int i=1;i<=n;i++) cout <<get(1,1,n,i,i)<<" ";
cout <<endl;*/
update1(1,1,n,l[i+1],1);
update1(1,1,n,r[i+1],1);
/* for (int i=1;i<=n;i++) cout <<get(1,1,n,i,i)<<" ";
cout <<endl;*/
}
ll len=C;
for (int i=1;i<=len;i++)
{
ll p=f[r[i]-1]-f[l[i]-1];
// cout <<l[i]<<" "<<r[i]<<" "<<"Wtf"<<endl;
// cout <<f[r[i]-1]<<" "<<r[i]-1<<" "<<f[l[i]-1]<<" "<<l[i]-1<<endl;
if (!p)
{
f1[l[i]]++;
f1[r[i]+1]--;
// cout <<"WTF"<<endl;
}
}
ll mx=-1;
int pos;
for (int i=1;i<=n;i++)
{
f1[i]+=f1[i-1];
if(f1[i]>mx)
{
mx=f1[i];
pos=i;
}
}
//cout <<mx<<endl;
return pos-1;
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("test.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
/*10 7 3
6
2
9
8
1
5
4
0
7
4 5
1 2
0 1
4 5
3 5
1 3
0 1
int k[20]={6, 2, 9, 8,1,5,4,0 , 7};
int s[20]={4,1,0,4,3,1,0};
int e[20]={5,2,1,5,5,3,1};
cout <<GetBestPosition(10,7,3,k,s,e);
int k[20];
int s[20];
int e[20];
ll n, c, r;
cin>> n>>c>> r;
for (int i=0;i<n-1;i++) cin>>k[i];
for (int i=0;i<c;i++)
{
cin>>s[i]>>e[i];
}
cout <<GetBestPosition(n,c,r,k,s,e);
}*/
Compilation message
tournament.cpp:189:5: warning: "/*" within comment [-Wcomment]
189 | /*10 7 3
|
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:177:16: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
177 | return pos-1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
332 KB |
Output is correct |
| 4 |
Correct |
2 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
2 ms |
332 KB |
Output is correct |
| 8 |
Correct |
2 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
300 KB |
Output is correct |
| 2 |
Correct |
21 ms |
824 KB |
Output is correct |
| 3 |
Correct |
5 ms |
644 KB |
Output is correct |
| 4 |
Correct |
17 ms |
804 KB |
Output is correct |
| 5 |
Correct |
16 ms |
760 KB |
Output is correct |
| 6 |
Correct |
12 ms |
728 KB |
Output is correct |
| 7 |
Correct |
17 ms |
848 KB |
Output is correct |
| 8 |
Correct |
17 ms |
844 KB |
Output is correct |
| 9 |
Correct |
2 ms |
588 KB |
Output is correct |
| 10 |
Correct |
18 ms |
836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
174 ms |
4612 KB |
Output is correct |
| 2 |
Correct |
556 ms |
10336 KB |
Output is correct |
| 3 |
Correct |
71 ms |
5316 KB |
Output is correct |
| 4 |
Correct |
588 ms |
10356 KB |
Output is correct |
| 5 |
Correct |
545 ms |
10052 KB |
Output is correct |
| 6 |
Correct |
382 ms |
9084 KB |
Output is correct |
| 7 |
Correct |
548 ms |
10224 KB |
Output is correct |
| 8 |
Correct |
559 ms |
10292 KB |
Output is correct |
| 9 |
Correct |
39 ms |
5016 KB |
Output is correct |
| 10 |
Correct |
71 ms |
7080 KB |
Output is correct |
