Submission #315696

#	Time	Username	Problem	Language	Result	Execution time	Memory
315696		talant117408	Jousting tournament (IOI12_tournament)	C++17	100 / 100	114 ms	20216 KiB

tournament

#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 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51