Submission #384332

#	Time	Username	Problem	Language	Result	Execution time	Memory
384332		jjang36524	Jousting tournament (IOI12_tournament)	C++14	100 / 100	102 ms	7012 KiB

tournament

    #include <algorithm>
    #include <string.h>
    #include <vector>
    using namespace std;
    int plu(int a,int b)
    {
        return a+b;
    }
    int maa(int a,int b)
    {
        return max(a,b);
    }
    struct segtree
    {
        int N,treeN;
        int stree[1<<20];
        int (*fp)(int,int);
        int ec;
        void init(int M,int (*p)(int,int),int e)
        {
            fp=p;
            ec=e;
            fill(stree,stree+(1<<10),ec);
            N=M;
            for(treeN=1;treeN<N;treeN*=2);
        }
        void upd(int n,int k)
        {
            n+=treeN;
            stree[n]=k;
            while(n!=1)
            {
                n/=2;
                stree[n]=fp(stree[n*2],stree[n*2+1]);
            }
        }
        int ge(int s,int e,int qs,int qe,int i)
        {
            if(s>qe||qs>e)
                return ec;
            if(qs<=s&&e<=qe)
                return stree[i];
            return fp(ge(s,(s+e)/2,qs,qe,i*2),ge((s+e)/2+1,e,qs,qe,i*2+1));
        }
        int kth(int s,int e,int i,int k)
        {
            if(s==e)
                return s;
            if(stree[i*2]<=k)
                return kth((s+e)/2+1,e,i*2+1,k-stree[i*2]);
            return kth(s,(s+e)/2,i*2,k);
        }
    }ma,kth;
    int to[1000010];
    int rs[1000010];
    int re[1000000];
    int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
    {
        ma.init(N-1,maa,0);
        kth.init(N+1,plu,0);
        int i;
        for(i=0;i<=N;i++)
        {
            kth.upd(i,1);
        }
        for(i=0;i<N-1;i++)
        {
            ma.upd(i,K[i]);
        }
        for(i=0;i<C;i++)
        {
            rs[i]=kth.kth(0,kth.treeN-1,1,S[i]);
            re[i]=kth.kth(0,kth.treeN-1,1,E[i]+1)-1;
            to[i]=ma.ge(0,ma.treeN-1,rs[i],re[i]-1,1);
            int j;
            for(j=S[i]+1;j<=E[i];j++)
            {
                kth.upd(kth.kth(0,kth.treeN-1,1,S[i]+1),0);
            }
        }
        vector<pair<int,int>>x;
        for(i=0;i<C;i++)
        {
            if(to[i]<R)
            {
                x.push_back({rs[i],1});
                x.push_back({re[i]+1,-1});
            }
        }
        sort(x.begin(),x.end());
        pair<int,int>an={0,0};
        int cu=0;
        for(i=0;i<x.size();i++)
        {
            cu+=x[i].second;
            an=max(an,{cu,-x[i].first});
        }
        return -an.second;
    }

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(i=0;i<x.size();i++)
      |                 ~^~~~~~~~~

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