Submission #895070

#	Time	Username	Problem	Language	Result	Execution time	Memory
895070		maxFedorchuk	Jousting tournament (IOI12_tournament)	C++17	100 / 100	76 ms	5424 KiB

tournament

#include <bits/stdc++.h>


using namespace std;

const long long MX=1e5+10;
int mas[4*MX];

int get_in(int v,int tl,int tr,int nd)
{
    if(tl==tr)
    {
        return tl;
    }

    int mid=(tl+tr)/2;

    if(nd<=mas[v*2])
    {
        return get_in(v*2,tl,mid,nd);
    }
    else
    {
        return get_in(v*2+1,mid+1,tr,nd-mas[v*2]);
    }
}

void upd(int v,int tl,int tr,int pos,int zn)
{
    if(tl==tr)
    {
        mas[v]+=zn;
        return;
    }

    int mid=(tl+tr)/2;

    if(pos<=mid)
    {
        upd(v*2,tl,mid,pos,zn);
    }
    else
    {
        upd(v*2+1,mid+1,tr,pos,zn);
    }

    mas[v]=mas[v*2]+mas[v*2+1];
    return;
}

int GetBestPosition(int n, int c, int r, int *k, int *s, int *e)
{
    int ans[n+1],win[n+1],link[n+1];

    for(int i=0;i<=n;i++)
    {
        win[i]=0;
        ans[i]=0;
    }

    for(int i=0;i<n;i++)
    {
        link[i]=i+1;
        upd(1,0,n,i,1);
        win[i+1]=win[i]+(k[i]>r);
    }

    for(int i=0;i<c;i++)
    {
        int l=get_in(1,0,n,s[i]+1);
        int r=get_in(1,0,n,e[i]+2);

        for(int j=link[l];j!=r;j=link[j])
        {
            upd(1,0,n,j,-1);
        }

        link[l]=r;

        r--;

        if(win[l]==win[r])
        {
            ans[l]++;
            ans[r]--;
        }
    }

    int in=0;
    for(int i=1;i<=n;i++)
    {
        ans[i]+=ans[i-1];
        if(ans[i]>ans[in])
        {
            in=i;
        }
    }

    return in;
}
/*
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n=5,c=3,r=3,k[4]={1,0,2,4},s[3]={1,0,0},e[3]={3,1,1};
    cout<<GetBestPosition(n,c,r,k,s,e)<<"\n";
    return 0;
}
*/
/*
#include <bits/stdc++.h>
using namespace std;

const int Z = 1 << 17;

int nxt[Z],cnt[Z*2];

int getnth(int n)
{
	int x = 1;

	while (x < Z){
		x <<= 1;
		if (cnt[x] < n) n -= cnt[x++];
	}

	return x - Z;
}

void up(int x, int p)
{
	x += Z;
	while (x){
		cnt[x] += p;
		x >>= 1;
	}
}

int add[Z],res[Z];




int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
	int i,peo,x,y;

	for (i=0;i<N;i++) nxt[i] = i+1, cnt[i+Z] = 1;
	for (i=Z-1;i>=1;i--) cnt[i] = cnt[i*2] + cnt[i*2+1];

	for (i=0;i<C;i++){
		peo = E[i] - S[i];
		S[i] = getnth(S[i]+1);
		x = nxt[S[i]];
		while (peo--){
			up(x,-1);
			x = nxt[x];
		}
		E[i] = x - 1;
		nxt[S[i]] = x;
	}

	for (i=1;i<N;i++) add[i] = add[i-1] + (K[i-1] > R);

	for (i=0;i<C;i++)
    {
        cout<<S[i]<<" "<<E[i]<<"\n";

		if (add[E[i]] == add[S[i]])
		{
			res[S[i]]++;
			res[E[i]]--;
		}
	}

	int s = 0, p = -1, ind;
	for (i=0;i<N;i++){
		s += res[i];
		if (p < s){
			p = s;
			ind = i;
		}
	}

	return ind;

}
int main()
{
    int n=5,c=3,r=3,k[4]={1,0,2,4},s[3]={1,0,0},e[3]={3,1,1};
    cout<<GetBestPosition(n,c,r,k,s,e)<<"\n";
}
*/

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