제출 #383221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383221		jjang36524	마상시합 토너먼트 (IOI12_tournament)	C++14	0 / 100	52 ms	9960 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<<20),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[100010];
int rs[100010];
int re[100000];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
    ma.init(N,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,j),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;
}

컴파일 시 표준 에러 (stderr) 메시지

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:93:14: 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: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51