Submission #372921

#	Time	Username	Problem	Language	Result	Execution time	Memory
372921		urd05	Jousting tournament (IOI12_tournament)	C++14	100 / 100	541 ms	33260 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

const int sz=262144;
int seg[sz*2];
int pos[200000];

int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return 0;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return sum(l,r,node*2,nodel,mid)+sum(l,r,node*2+1,mid+1,noder);
}

void update(int i,int val) {
    i+=sz;
    seg[i]+=val;
    while (i>1) {
        i/=2;
        seg[i]=seg[i*2]+seg[i*2+1];
    }
}

int find(int k,int node=1) {
    if (node>=sz) {
        return node-sz;
    }
    if (seg[node*2]>k) {
        return find(k,node*2);
    }
    else {
        return find(k-seg[node*2],node*2+1);
    }
}

vector<int> son[200000];
int cnt;
int f=0;
int ind[200000];
int par[200000][18];
int sub[200000];

void dfs(int v) {
    ind[v]=f++;
    sub[v]=1;
    for(int i=0;i<son[v].size();i++) {
        dfs(son[v][i]);
        sub[v]+=sub[son[v][i]];
    }
}

int GetBestPosition(int n,int c,int r,int *K, int *S, int *E) {
    for(int i=0;i<n;i++) {
        pos[i]=i;
        update(i,1);
    }
    cnt=n;
    memset(par,-1,sizeof(par));
    for(int i=0;i<c;i++) {
        int now=find(S[i]);
        int save=pos[now];
        pos[now]=cnt++;
        son[pos[now]].push_back(save);
        par[save][0]=pos[now];
        for(int j=S[i]+1;j<=E[i];j++) {
            int got=find(S[i]+1);
            son[pos[now]].push_back(pos[got]);
            par[pos[got]][0]=pos[now];
            update(got,-1);
        }
    }
    for(int j=1;j<18;j++) {
        for(int i=0;i<cnt;i++) {
            if (par[i][j-1]!=-1) {
                par[i][j]=par[par[i][j-1]][j-1];
            }
        }
    }
    memset(seg,0,sizeof(seg));
    dfs(cnt-1);
    for(int i=0;i<n-1;i++) {
        if (K[i]>r) {
            update(ind[i+1],1);
        }
    }
    int mx=-1;
    int ret=-1;
    for(int pos=0;pos<n;pos++) {
        int now=pos;
        int val=0;
        for(int i=17;i>=0;i--) {
            int nt=par[now][i];
            if (nt==-1) {
                continue;
            }
            if (sum(ind[nt],ind[nt]+sub[nt]-1)==0) {
                now=nt;
                val+=(1<<i);
            }
        }
        if (val>mx) {
            ret=pos;
            mx=val;
        }
        if (pos!=n-1) {
            if (K[pos]>r) {
                update(ind[pos+1],-1);
                update(ind[pos],1);
            }
        }
    }
    return ret;
}

Compilation message (stderr)

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

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