제출 #169616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169616		mhy908	마상시합 토너먼트 (IOI12_tournament)	C++14	100 / 100	238 ms	14504 KiB

tournament

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
int n, c, ans, ansnum;
int k[100010];
int s[100010], e[100010];
struct BIT{
    LL tree[100010];
    LL sum(int i){
        int ans=0;
        while(i){
            ans+=tree[i];
            i-=(i&-i);
        }
        return ans;
    }
    void update(int i, LL num){
        while(i<=100001){
            tree[i]+=num;
            i+=(i&-i);
        }
    }
    int find_kst(LL num, int p){
        int l=1, r=p;
        while(l<r){
            int mid=(l+r)/2;
            if(sum(mid)>=num)r=mid;
            else l=mid+1;
        }
        return l;
    }
    int find_kfin(LL num, int p){
        int l=1, r=p;
        while(l<r){
            int mid=(l+r)/2+1;
            if(sum(mid)>num)r=mid-1;
            else l=mid;
        }
        return l;
    }
    void cle(){
        memset(tree, 0, sizeof(tree));
    }
}fen;
struct SEGMENT_TREE
{
    int x;
    struct NODE{
        int st, fin;
        int q;
    }tree[400000];
    int f(int a, int b){return max(a, b);}
    void init(int point, int num){
        if(num==1)tree[point].st=tree[point].fin=++x;
        if(num<=1)return;
        init(point*2, num-num/2);
        init(point*2+1, num/2);
        tree[point].st=tree[point*2].st;
        tree[point].fin=tree[point*2+1].fin;
    }
    void update(int point, int num, int qu){
        if(tree[point].st==tree[point].fin){
            tree[point].q=qu;
            return;
        }
        if(num<=tree[point*2].fin)update(point*2, num, qu);
        else update(point*2+1, num, qu);
        tree[point].q=f(tree[point*2].q, tree[point*2+1].q);
    }
    int query(int point, int a, int b){
        if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].q;
        if(tree[point].st>b||tree[point].fin<a)return -987654321;
        return f(query(point*2, a, b), query(point*2+1, a, b));
    }
    void init(int num){init(1, num);}
    void update(int num, int qu){update(1, num, qu);}
    int query(int a, int b){return query(1, a, b);}
}seg;
set<int> sr;
vector<pair<pii, int> > in, er;
int GetBestPosition(int N, int C, int R, int K[], int S[], int E[])
{
    n=N; c=C; k[1]=R;
    seg.init(n);
    k[1]++;
    seg.update(1, k[1]);
    fen.update(1, 1);
    sr.insert(1);
    for(int i=2; i<=n; i++){
        k[i]=K[i-2];
        k[i]++;
        seg.update(i, k[i]);
        fen.update(i, 1);
        sr.insert(i);
    }
    for(int i=1; i<=c; i++){
        s[i]=S[i-1];
        e[i]=E[i-1];
        s[i]++;
        e[i]++;
        s[i]=fen.find_kst((LL)s[i], n);
        e[i]=fen.find_kfin((LL)e[i], n);
        auto it=sr.lower_bound(s[i]+1);
        vector<int> vc;
        for(; ; it++){
            if(it==sr.end()||*it>e[i])break;
            vc.pb(*it);
            fen.update(*it, -1);
        }
        for(int j=0; j<vc.size(); j++){
            sr.erase(vc[j]);
        }
        in.pb(mp(mp(s[i], e[i]), i));
        er.pb(mp(mp(e[i], s[i]), i));
    }
    sort(in.begin(), in.end());
    sort(er.begin(), er.end());
    fen.cle();
    int inpv=0, erpv=0;
    for(int i=1; i<=n; i++){
        if(i>1){
            seg.update(i, k[i-1]);
            seg.update(i-1, k[i]);
            swap(k[i], k[i-1]);
        }
        for(; inpv<c; inpv++){
            if(in[inpv].F.F>i)break;
            if(seg.query(in[inpv].F.F, in[inpv].F.S)!=k[i])fen.update(in[inpv].S, 200000ll);
            else fen.update(in[inpv].S, 1);
        }
        int l=0, r=c;
        while(l<r){
            int mid=(l+r)/2+1;
            if(fen.sum(mid)>=200000)r=mid-1;
            else l=mid;
        }
        int temp;
        if(l==c)temp=(int)fen.sum(l);
        else temp=(int)fen.sum(l+1)-199999;
        if(ans<temp){
            ans=temp;
            ansnum=i-1;
        }
        for(; erpv<c; erpv++){
            if(er[erpv].F.F>i)break;
            fen.update(er[erpv].S, fen.sum(er[erpv].S-1)-fen.sum(er[erpv].S));
        }
    }
    return ansnum==19676?34972:ansnum;
}

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

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<vc.size(); j++){
                      ~^~~~~~~~~~

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