oj.uz

Submission #109566

# Submission time Handle Problem Language Result Execution time Memory
109566 2019-05-07T06:07:06 Z nvmdava Jousting tournament (IOI12_tournament) C++17
100 / 100
 57 ms 5596 KB 
#include <bits/stdc++.h>
using namespace std;
#define BIG 131072

int fen[BIG];
int in[BIG];
int p[BIG];
int last[BIG];
int ans[BIG];
int N;
int find(int v){
    return in[v] == 1 ? v : p[v] = find(p[v]);
}

void upd(int loc){
    while(loc < BIG){
        fen[loc]--;
        loc += loc & -loc;
    }
}

void rangeupd(int l, int r){
    while((l = find(p[l])) <= r){
        in[l] = 0;
        upd(l);
    }
}

int finder(int val){
    int res = 0;
    int id = 0;
    for(int i = 16; i >= 0; i--){
        if(res + fen[id + (1 << i)] < val){
            id += 1 << i;
            res += fen[id];
        }
    }
    return id+1;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
    for(int i = 1; i <= N; i++){
        p[i] = i + 1;
        in[i] = 1;
    }
    for(int i = 1; i < BIG; i++){
        fen[i] = i & -i;
        in[i] = 1;
    }

    for(int i = 0; i < N - 1; i++){
        last[i + 1] = last[i];
        if(K[i] > R) last[i + 1] = i + 1;
    }
    last[N] = last[N - 1];
    for(int i = 0; i < C; i++){
        S[i] = finder(S[i] + 1);
        E[i] = find(p[finder(E[i] + 1)]) - 1;
        rangeupd(S[i], E[i]);
        if(last[E[i] - 1] < S[i]){
            ans[S[i]]++;
            ans[E[i] + 1]--;
        }
    }
    int ret = 1;
    for(int i = 1; i < BIG; i++){
        ans[i] += ans[i - 1];
        if(ans[i] > ans[ret]) ret = i;
    }
    return ret - 1;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1920 KB Output is correct
2 Correct 5 ms 2048 KB Output is correct
3 Correct 4 ms 1920 KB Output is correct
4 Correct 4 ms 1920 KB Output is correct
5 Correct 4 ms 1920 KB Output is correct
6 Correct 4 ms 1920 KB Output is correct
7 Correct 5 ms 1920 KB Output is correct
8 Correct 4 ms 1920 KB Output is correct
9 Correct 4 ms 1920 KB Output is correct
10 Correct 4 ms 1920 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1920 KB Output is correct
2 Correct 6 ms 2048 KB Output is correct
3 Correct 5 ms 2176 KB Output is correct
4 Correct 7 ms 2048 KB Output is correct
5 Correct 6 ms 2048 KB Output is correct
6 Correct 5 ms 2048 KB Output is correct
7 Correct 6 ms 2048 KB Output is correct
8 Correct 6 ms 2048 KB Output is correct
9 Correct 5 ms 2048 KB Output is correct
10 Correct 8 ms 2048 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3320 KB Output is correct
2 Correct 57 ms 5484 KB Output is correct
3 Correct 23 ms 5240 KB Output is correct
4 Correct 54 ms 5496 KB Output is correct
5 Correct 52 ms 5368 KB Output is correct
6 Correct 55 ms 4856 KB Output is correct
7 Correct 55 ms 5596 KB Output is correct
8 Correct 57 ms 5496 KB Output is correct
9 Correct 20 ms 4992 KB Output is correct
10 Correct 22 ms 3704 KB Output is correct