oj.uz

Submission #109569

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

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

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

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

inline int finder(int val){
    int res = 0;
    int id = 0;
    for(int i = 16; i >= 0; i--){
        if(id + (1 << i) <= N && 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) {
    int i;
    ::N = N;
    for(i = 1; i <= N; i++)
        p[i] = i + 1;
    for(i = 1; i < BIG; i++){
        fen[i] = i & -i;
        in[i] = 1;
    }

    for(i = 1; i < N; i++){
        if(K[i - 1] > R) last[i] = i;
        else last[i] = last[i - 1];
    }
    last[N] = last[N - 1];
    for(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(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 1536 KB Output is correct
2 Correct 7 ms 1528 KB Output is correct
3 Correct 3 ms 1464 KB Output is correct
4 Correct 3 ms 1536 KB Output is correct
5 Correct 3 ms 1536 KB Output is correct
6 Correct 5 ms 1536 KB Output is correct
7 Correct 3 ms 1536 KB Output is correct
8 Correct 3 ms 1536 KB Output is correct
9 Correct 3 ms 1536 KB Output is correct
10 Correct 4 ms 1536 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1452 KB Output is correct
2 Correct 6 ms 1536 KB Output is correct
3 Correct 5 ms 1664 KB Output is correct
4 Correct 5 ms 1636 KB Output is correct
5 Correct 7 ms 1664 KB Output is correct
6 Correct 6 ms 1552 KB Output is correct
7 Correct 6 ms 1532 KB Output is correct
8 Correct 8 ms 1536 KB Output is correct
9 Correct 5 ms 1588 KB Output is correct
10 Correct 8 ms 1536 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2284 KB Output is correct
2 Correct 57 ms 3420 KB Output is correct
3 Correct 35 ms 4100 KB Output is correct
4 Correct 60 ms 3384 KB Output is correct
5 Correct 63 ms 3320 KB Output is correct
6 Correct 59 ms 3200 KB Output is correct
7 Correct 63 ms 3444 KB Output is correct
8 Correct 56 ms 3400 KB Output is correct
9 Correct 22 ms 3968 KB Output is correct
10 Correct 24 ms 2680 KB Output is correct