Submission #223667

#	Time	Username	Problem	Language	Result	Execution time	Memory
223667		laoriu	Jousting tournament (IOI12_tournament)	C++14	0 / 100	89 ms	9976 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pp;
struct node
{
    int num,r,d;
};
node it[400002];
int f[100002],ll[100002],rr[100002];
int rmq[100002][22];
void update(int id,int l,int r,int pos,node a)
{
    if (l>pos||r<pos) return;
    if (l==r)
    {
        it[id].num=a.num;it[id].r=a.r;
        it[id].d=a.d;return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,pos,a);
    update(id*2+1,mid+1,r,pos,a);
    it[id].num=it[id*2].num+it[id*2+1].num;
    it[id].r=max(it[id*2].r,it[id*2+1].r);
    it[id].d=max(it[id*2].d,it[id*2+1].d);
}
pp query(int id,int l,int r,int a,int b)
{
    if (l>b||r<a) return {0,0};
    if (l>=a&&r<=b)
    {
        return {it[id].r,it[id].d};
    }
    int mid=(l+r)/2;
    pp x=query(id*2,l,mid,a,b);
    pp y=query(id*2+1,mid+1,r,a,b);
    return {max(x.first,y.first),max(x.second,y.second)};
}
int find_pos(int id,int l,int r,int k)
{
    if (l==r) return l;
    int mid=(l+r)/2;
    if (it[id*2].num>=k) return find_pos(id*2,l,mid,k);
    else return find_pos(id*2+1,mid+1,r,k-it[id*2].num);
}
int GetBestPosition(int n,int k,int r,int A[],int L[],int R[])
{
    for (int i=n-1;i>=1;i--) A[i]=A[i-1];
    for (int i=1;i<=n;i++)
        update(1,1,n,i,{1,i,0});
    set <int> s;
    set <int>::iterator id;
    for (int i=1;i<=n;i++) s.insert(i);
    for (int i=0;i<k;i++)
    {
        L[i]++;R[i]++;
        int l=find_pos(1,1,n,L[i]);int r=find_pos(1,1,n,R[i]);
        pp a=query(1,1,n,l,r);
        f[i]=a.second+1;ll[i]=l;rr[i]=a.first;
        id=s.lower_bound(l);
        for (id;id!=s.end();id++)
        {
            if ((*id)>r) break;
            if ((*id)!=l) update(1,1,n,(*id),{0,0,0});

        }
        id=s.lower_bound(l);
        for (id;id!=s.end();id++)
        {
            if ((*id)>r) break;
            if ((*id)!=l) s.erase(id);
        }
        update(1,1,n,l,{1,rr[i],f[i]});

    }
    for (int i=1;i<=n;i++) rmq[i][0]=A[i];
    for (int j=1;j<=20;j++)
        for (int i=1;i<=n;i++)
            if (i>=(1<<j))
        {
            rmq[i][j]=max(rmq[i][j-1],rmq[i-(1<<(j-1))][j-1]);
        }

    int res=0;
    for (int i=0;i<k;i++)
    {
        int vmax=0;
        for (int j=0;j<=20;j++)
            if ((1<<j)>rr[i]-ll[i]) break;
            else vmax=max(vmax,max(rmq[rr[i]-1][j],rmq[ll[i]+(1<<j)-1][j]));
        if(r>vmax) res=max(res,f[i]);
    }
    return res;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:60:16: warning: statement has no effect [-Wunused-value]
         for (id;id!=s.end();id++)
                ^
tournament.cpp:67:16: warning: statement has no effect [-Wunused-value]
         for (id;id!=s.end();id++)
                ^

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