Submission #887868

#	Time	Username	Problem	Language	Result	Execution time	Memory
887868		JakobZorz	Jousting tournament (IOI12_tournament)	C++17	100 / 100	105 ms	6960 KiB

tournament

#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int TREE_SIZE=1<<17;

int max_tree[2*TREE_SIZE];
void set_max_tree(int i,int v){
    int node=TREE_SIZE+i;
    max_tree[node]=v;
    node/=2;
    while(node){
        max_tree[node]=max(max_tree[2*node],max_tree[2*node+1]);
        node/=2;
    }
}

int get_max(int node,int l,int r,int rl,int rr){
    if(r<=rl||rr<=l)
        return 0;
    if(l<=rl&&rr<=r)
        return max_tree[node];
    
    int mid=(rl+rr)/2;
    return max(get_max(2*node,l,r,rl,mid),get_max(2*node+1,l,r,mid,rr));
}

int get_max(int l,int r){
    return get_max(1,l,r,0,TREE_SIZE);
}

bool get_interval(int left,int right,int r){
    right--;
    int m=get_max(left,right);
    return m<r;
}

int tree[2*TREE_SIZE];
void init_tree(){
    for(int i=TREE_SIZE;i<2*TREE_SIZE;i++)
        tree[i]=1;
    for(int i=TREE_SIZE-1;i>0;i--)
        tree[i]=tree[2*i]+tree[2*i+1];
}

void set_interval(int node,int l,int r,int rl,int rr){
    if(r<=rl||rr<=l){
        return;
    }
    if(l<=rl&&rr<=r){
        tree[node]=0;
        return;
    }
    
    int mid=(rl+rr)/2;
    set_interval(2*node,l,r,rl,mid);
    set_interval(2*node+1,l,r,mid,rr);
    tree[node]=tree[2*node]+tree[2*node+1];
}

int get_index(int node,int sum,int rl,int rr){
    //cout<<node<<" "<<sum<<" "<<rl<<" "<<rr<<" "<<tree[node]<<endl;
    if(sum==0)
        return rl;
    if(rl==rr-1&&sum==1)
        return rr;
    
    if(tree[node]==0&&node<TREE_SIZE){
        tree[2*node]=0;
        tree[2*node+1]=0;
    }
    
    int mid=(rl+rr)/2;
    if(sum>tree[2*node]){
        return get_index(2*node+1,sum-tree[2*node],mid,rr);
    }else{
        return get_index(2*node,sum,rl,mid);
    }
}

int GetBestPosition(int n,int c,int r,int *K,int *L,int *R){
    for(int i=0;i<c;i++)
        R[i]++;
    vector<int>present(n,1);
    init_tree();
    for(int j=0;j<c;j++){
        int sum=0;
        int l=n,r=n;
        for(int i=0;i<n;i++){
            if(sum==L[j]&&l==n)
                l=i;
            if(sum==R[j]&&r==n)
                r=i;
            sum+=present[i];
        }
        /*L[j]=l;
        R[j]=r;
        for(int i=l;i<r-1;i++)
            present[i]=0;*/
        
        L[j]=get_index(1,L[j],0,TREE_SIZE);
        R[j]=get_index(1,R[j],0,TREE_SIZE);
        //cout<<L[j]<<" "<<l<<endl;
        //cout<<R[j]<<" "<<r<<endl;
        set_interval(1,L[j],R[j]-1,0,TREE_SIZE);
    }
    
    //cout<<"the end"<<endl;
    
    for(int i=0;i<n-1;i++)
        set_max_tree(i,K[i]);
    
    int max_res=-1;
    int i_res=0;
    
    vector<pair<int,int>>ranges1(c),ranges2(c);
    for(int i=0;i<c;i++){
        ranges1[i]={L[i],R[i]};
        ranges2[i]={R[i],L[i]};
    }
    
    sort(ranges1.begin(),ranges1.end());
    sort(ranges2.begin(),ranges2.end());
    int i1=0,i2=0;
    int res=0;
    
    for(int ins=0;ins<n;ins++){
        while(i1<c&&ranges1[i1].first==ins){
            res+=get_interval(ranges1[i1].first,ranges1[i1].second,r);
            i1++;
        }
        
        while(i2<c&&ranges2[i2].first==ins){
            res-=get_interval(ranges2[i2].second,ranges2[i2].first,r);
            i2++;
        }
        
        //cout<<res<<"\n";
        
        if(res>max_res){
            max_res=res;
            i_res=ins;
        }
    }
    
    
    
    return i_res;
}

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