oj.uz

Submission #315696

# Submission time Handle Problem Language Result Execution time Memory
315696 2020-10-23T16:53:22 Z talant117408 Jousting tournament (IOI12_tournament) C++17
100 / 100
 114 ms 20216 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int MAXN = 100007;
int n, ranks[MAXN], s[MAXN], e[MAXN];

struct Tree{
    private:
        vector <int> tree, lz;
    public:
        Tree(int n){
            tree.assign(n*4, 0);
        }
        void build(int v, int l, int r){
            if(l == r){
                tree[v] = 1;
                return;
            }
            int mid = (l+r) >> 1;
            build(v<<1, l, mid);
            build((v<<1)+1, mid+1, r);
            tree[v] = tree[v<<1] + tree[(v<<1)+1];
        }
        void update(int v, int l, int r, int ql, int qr){ // превращаем все элементы с ql до qr в нули
            if(qr < l || r < ql) return;
            if(ql <= l && r <= qr){
                tree[v] = 0;
                return;
            }
            int mid = (l+r) >> 1;
            update(v<<1, l, mid, ql, qr);
            update((v<<1)+1, mid+1, r, ql, qr);
            tree[v] = tree[v<<1] + tree[(v<<1)+1];
        }
        int get(int v, int l, int r, int k){ // находим k-ную единицу
            if(l == r){
                return l;
            }
            int mid = (l+r) >> 1;
            if(k <= tree[v<<1]){
                return get(v<<1, l, mid, k);
            }
            else{
                return get((v<<1)+1, mid+1, r, k-tree[v<<1]);
            }
        }
        int quan(){
            return tree[1];
        }
} tree(MAXN);

bool cmp(pii a, pii b){
    if(a.first == b.first) return a.second > b.second;
    return a.first < b.first;
}

vector <pii> ranges;
vector <int> pref;
vector <vector <int>> graph(MAXN);
int sub[MAXN], pos[MAXN];

pii dfs(int u, int p = -1){
    int mx = 0, in = ranges[u].first;
    for(auto to : graph[u]){
        if(to != p){
            auto it = dfs(to, u);
            if(it.first > mx){
                mx = it.first;
                in = it.second;
            }
        }
    }
    if(pref[ranges[u].second-1]-pref[ranges[u].first-1] == 0){
        sub[u] = mx+1;
    }
    else{
        sub[u] = mx;
    }
    pos[u] = in;
    return mp(sub[u], pos[u]);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
    int i;
    n = N;
    
    for(i = 0; i < n-1; i++){
        ranks[i+1] = K[i];
    }
    for(i = 0; i < C; i++){
        s[i+1] = S[i]+1;
        e[i+1] = E[i]+1;
    }
    
    tree.build(1, 1, n);
    
    for(i = 1; i <= C; i++){
        int s1 = tree.get(1, 1, n, s[i]);
        if(tree.quan() < e[i]+1){
            ranges.pb(mp(s1, n));
            tree.update(1, 1, n, s1+1, n);
        }
        else{
            int e1 = tree.get(1, 1, n, e[i]+1)-1;
            ranges.pb(mp(s1, e1));
            tree.update(1, 1, n, s1+1, e1);
        }
    }
    
    sort(all(ranges), cmp);
    pref.assign(n+1, 0);
    
    for(i = 1; i < n; i++){
        pref[i] += pref[i-1];
        if(ranks[i] > R) pref[i]++;
    }
    
    for(i = 1; i < sz(ranges); i++){
        int j = i-1;
        while(!(ranges[j].first <= ranges[i].first && ranges[j].second >= ranges[i].second)) j--;
        graph[i].pb(j);
        graph[j].pb(i);
    }
    
    auto ans = dfs(0);
    return --ans.second;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4352 KB Output is correct
2 Correct 8 ms 4992 KB Output is correct
3 Correct 4 ms 4352 KB Output is correct
4 Correct 8 ms 4736 KB Output is correct
5 Correct 7 ms 4864 KB Output is correct
6 Correct 7 ms 4608 KB Output is correct
7 Correct 8 ms 4864 KB Output is correct
8 Correct 8 ms 4864 KB Output is correct
9 Correct 4 ms 4352 KB Output is correct
10 Correct 8 ms 4736 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6900 KB Output is correct
2 Correct 114 ms 20216 KB Output is correct
3 Correct 28 ms 6520 KB Output is correct
4 Correct 112 ms 15792 KB Output is correct
5 Correct 109 ms 17132 KB Output is correct
6 Correct 84 ms 10608 KB Output is correct
7 Correct 110 ms 17388 KB Output is correct
8 Correct 110 ms 17260 KB Output is correct
9 Correct 21 ms 6016 KB Output is correct
10 Correct 27 ms 6392 KB Output is correct