oj.uz

Submission #384332

# Submission time Handle Problem Language Result Execution time Memory
384332 2021-04-01T11:39:35 Z jjang36524 Jousting tournament (IOI12_tournament) C++14
100 / 100
 102 ms 7012 KB 
    #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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 5 ms 620 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 6 ms 620 KB Output is correct
5 Correct 5 ms 736 KB Output is correct
6 Correct 7 ms 748 KB Output is correct
7 Correct 5 ms 748 KB Output is correct
8 Correct 5 ms 620 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 6 ms 748 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2664 KB Output is correct
2 Correct 102 ms 6632 KB Output is correct
3 Correct 44 ms 3308 KB Output is correct
4 Correct 98 ms 7012 KB Output is correct
5 Correct 98 ms 6780 KB Output is correct
6 Correct 96 ms 6156 KB Output is correct
7 Correct 101 ms 7012 KB Output is correct
8 Correct 98 ms 7012 KB Output is correct
9 Correct 38 ms 2924 KB Output is correct
10 Correct 43 ms 3052 KB Output is correct