Submission #587006

#	Time	Username	Problem	Language	Result	Execution time	Memory
587006		mosiashvililuka	Jousting tournament (IOI12_tournament)	C++14	17 / 100	1086 ms	10452 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,R,f[100009],seg[400009],seg2[400009],l,r,z,za,Z,msh[400009],cnt,mx[400009],ans[400009],g[100009];
vector <int> v[400009];
set <pair <int, int> > s;
set <pair <int, int> >::iterator it,tt;
void pushdown(int q, int w, int rr){
    if(q!=w){
        seg2[rr*2]+=seg2[rr];
        seg2[rr*2+1]+=seg2[rr];
    }
    seg[rr]+=seg2[rr];
    seg2[rr]=0;
}
void upd(int q, int w, int rr){
    pushdown(q,w,rr);
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        seg2[rr]=z;
        pushdown(q,w,rr);
        return;
    }
    upd(q,(q+w)/2,rr*2);
    upd((q+w)/2+1,w,rr*2+1);
    seg[rr]=max(seg[rr*2],seg[rr*2+1]);
}
void read(int q, int w, int rr){
    if(q==w){
        z=q;
        return;
    }
    pushdown(q,(q+w)/2,rr*2);
    pushdown((q+w)/2+1,w,rr*2+1);
    if(seg[rr*2]<Z){
        read((q+w)/2+1,w,rr*2+1);
    }else{
        read(q,(q+w)/2,rr*2);
    }
}
void dfs(int q, int w){
    if(q<=a){
        mx[q]=f[q];
        return;
    }
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it)==w) continue;
        dfs((*it),q);
        mx[q]=max(mx[q],mx[(*it)]);
    }
}
void dfs2(int q, int w, int rr){
    if(mx[q]>R) rr=0;
    if(q<=a){
        ans[q]=rr-1;
        return;
    }
    for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        if((*it)==w) continue;
        dfs2((*it),q,rr+1);
    }
}
int GetBestPosition(int NN, int CC, int RR, int *KK, int *SS, int *EE) {
    a=NN;tes=CC;R=RR;R++;
    for(i=2; i<=a; i++){
        f[i]=KK[i-2];f[i]++;
    }
    for(i=1; i<a; i++){
        g[i]=f[i+1];
    }
    zx=-1;xc=-1;
    for(ii=1; ii<=a; ii++){
        for(i=1; i<=a; i++){
            if(i<ii){
                f[i]=g[i];
                continue;
            }
            if(i==ii){
                f[i]=R;
                continue;
            }
            f[i]=g[i-1];
        }
        e=0;
        for(t=1; t<=tes; t++){
            c=SS[t-1]+1;d=EE[t-1]+1;
            int mx1=0,mx2=0,E=0;
            for(i=c; i<=d; i++){
                if(f[i]==R) E=1;
                if(mx1<f[i]){
                    mx1=f[i];mx2=i;
                }
            }
            if(E==1){
                if(mx1==R){
                    e++;
                }else{
                    break;
                }
            }
            f[c]=f[mx2];
            for(i=c+1; ; i++){
                j=i+(d-c);
                if(f[j]==0) break;
                f[i]=f[j];
            }
        }
        if(zx<e){
            zx=e;xc=ii;
        }
    }
    return xc-1;
}

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