oj.uz

Submission #887825

# Submission time Handle Problem Language Result Execution time Memory
887825 2023-12-15T09:24:45 Z JakobZorz Jousting tournament (IOI12_tournament) C++17
17 / 100
 1000 ms 1372 KB 
#include<vector>
#include<iostream>
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);
}

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);
    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;
        //cout<<l<<" "<<r<<"\n";
        for(int i=l;i<r-1;i++)
            present[i]=0;
    }
    
    for(int i=0;i<n-1;i++)
        set_max_tree(i,K[i]);
    
    int max_res=-1;
    int i_res=0;
    
    for(int ins=0;ins<n;ins++){
        //(int i:arr)
            //cout<<i<<" ";
        //cout<<"\n";
        int res=0;
        
        for(int j=0;j<c;j++){
            int left=L[j];
            int right=R[j];
            
            if(left>ins)
                continue;
            if(right<=ins)
                continue;
            
            right--;
            int m=get_max(left,right);
            if(m<r)
                res++;
        }
        
        //cout<<ins<<" "<<res<<"\n";
        
        if(res>max_res){
            max_res=res;
            i_res=ins;
        }
    }
    
    
    
    return i_res;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 6 ms 600 KB Output is correct
4 Correct 15 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 348 KB Output is correct
7 Correct 10 ms 492 KB Output is correct
8 Correct 9 ms 644 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Execution timed out 1096 ms 556 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1043 ms 1372 KB Time limit exceeded
2 Halted 0 ms 0 KB -