Submission #424104

#	Time	Username	Problem	Language	Result	Execution time	Memory
424104		Dymo	Jousting tournament (IOI12_tournament)	C++14	0 / 100	183 ms	4624 KiB

tournament

#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;
    }

    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];
        if (!p)
        {
           f1[l[i]]++;
           f1[r[i]+1]--;
        }
    }
    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("Fgarden.inp", "r"))
    {
        freopen("Fgarden.inp", "r", stdin);
        freopen("Fgarden.out", "w", stdout);
    }
    int k[10]={1, 0, 2, 4};
     int s[10]={1,0,0};
     int e[10]={3,1,1};
    cout <<GetBestPosition(5,3,3,k,s,e);
}*/

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:172:16: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  172 |     return pos-1;
      |                ^

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51