oj.uz

Submission #38873

# Submission time Handle Problem Language Result Execution time Memory
38873 2018-01-07T13:08:05 Z andy627 Jousting tournament (IOI12_tournament) C++14
0 / 100
 33 ms 5792 KB 
#include <stdio.h>
#include <set>
#include <algorithm>
#define ff first
#define ss second
#define pii pair<int,int>
#define ele 131072
using namespace std;

int n,c,r;
int k[111111],s[111111],e[111111];
int nxt[111111],idx[333333];
set<pii> eff;

void put_(int p,int num){
    for(p+=ele-1,idx[p]=num,p>>=1;p;p>>=1) idx[p]=max(idx[2*p],idx[2*p+1]);
}

int max_(int s,int e){
    int mx=0;
    s+=ele-1; e+=ele-1;
    while(s<e){
        if(s%2==1) mx=max(mx,idx[s++]);
        if(e%2==0) mx=max(mx,idx[e--]);
        s/=2; e/=2;
    }
    if(s==e) mx=max(mx,idx[s]);

    return mx;
}

int GetBestPosition(int N,int C,int R,int *K,int *S,int *E){
    n=N; c=C; r=R;
    for(int i=0;i<N-1;i++) k[i]=K[i];
    for(int i=0;i<C;i++) s[i]=S[i];
    for(int i=0;i<C;i++) e[i]=E[i];

    for(int i=0;i<n;i++) nxt[i]=i+1;
    for(int i=0;i<n-1;i++) put_(i+1,k[i]);

    for(int i=0;i<c;i++){
        int del=e[i]-s[i]; e[i]=s[i];
        for(int j=0;j<=del;j++) e[i]=nxt[e[i]];
        nxt[s[i]]=e[i]; e[i]--;
    }
/*
    for(int i=0;i<c;i++) printf("%d %d\n",s[i],e[i]);
    printf("\n");
*/
    for(int i=0;i<c;i++){
        if(r==max(r,max_(s[i]+1,e[i]))){
            eff.insert({s[i],1});
            eff.insert({e[i]+1,-1});
        }
    }
/*
    set<pii>::iterator itt=eff.begin();
    while(itt!=eff.end()) printf("%d %d\n",itt->ff,itt->ss),itt++;
    printf("\n");
*/
    int mx=0,res=0;
    set<pii>::iterator it=eff.begin();
    for(int i=0;i<n;i++){
        while(it!=eff.end() && it->ff==i) res+=it->ss,it++;
        mx=max(mx,res);
    }

    return mx;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4208 KB Output is correct
2 Incorrect 0 ms 4208 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 5792 KB Output isn't correct
2 Halted 0 ms 0 KB -