oj.uz

Submission #761443

# Submission time Handle Problem Language Result Execution time Memory
761443 2023-06-19T16:17:15 Z fatemetmhr Jousting tournament (IOI12_tournament) C++17
100 / 100
 84 ms 69140 KB 
//  ~ Be Name Khoda ~  //

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  (1 << 19)   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const int lg    =  19;
const ll  inf   =  1e18;

vector <int> adj[maxn5];
int par[lg][maxn5], l[maxn5], pre[maxn5];
int r[maxn5], id[maxn5], nxt[maxn5], pos[maxn5];

namespace fen{

    int fen[maxn5];

    inline void add(int id, int val){
        for(++id; id < maxn5; id += id & -id)
            fen[id] += val;
    }

    inline int find(int k){
        //cout << "finding " << k << endl;
        int id = 0;
        for(int i = lg - 1; i >= 0; i--){
            //cout << "check for " << i << ' ' << id << ' ' << k << ' ' << fen[id + (1 << i)] << endl;
            if(fen[id + (1 << i)] < k){
                id += (1 << i);
                k -= fen[id];
            }
        }
        //cout << "id of " << id << ' ' << k << endl;
        return id;
    }
}

void dfs(int v){
    //cout << "ok " << v << ' ' << par[0][v] << endl;
    for(int i = 1; i < lg && par[i - 1][v] != -1; i++)
        par[i][v] = par[i - 1][par[i - 1][v]];
    if(adj[v].empty()){
        l[v] = r[v] = v;
        return;
    }
    l[v] = mod; r[v] = 0;
    for(auto u : adj[v]){
        par[0][u] = v;
        dfs(u);
        l[v] = min(l[v], l[u]);
        r[v] = max(r[v], r[u]);
    }
}

inline int get_sum(int *k, int l, int r){
    return k[r] - (l ? k[l - 1] : 0);
}


int GetBestPosition(int n, int c, int r, int *k, int *s, int *e){

    for(int i = 0; i < n; i++){
        fen::add(i, 1);
        pre[i] = i - 1;
        nxt[i] = i + 1;
        id[i] = i;
        pos[i] = i;
    }
    int newnode = n;
    nxt[n - 1] = -1;
    for(int i = 0; i < c; i++){
        int st = fen::find(s[i] + 1);
        int x = id[st];
        int v = pre[x];
        int z = newnode++;
        id[st] = z;
        pos[z] = st;
        int tt = e[i] - s[i];
        adj[z].pb(x);
        while(tt--){
            x = nxt[x];
            fen::add(pos[x], -1);
            adj[z].pb(x);
        }
        int u = nxt[x];
        if(u != -1)
            pre[u] = z;
        nxt[z] = u;
        if(v != -1)
            nxt[v] = z;
        pre[z] = v;
    }

    int root = newnode - 1;
    memset(par, -1, sizeof par);
    for(int i = 0; i < n - 1; i++){
        k[i] = (k[i] > r);
        if(i)
            k[i] += k[i - 1];
    }
    dfs(root);
    int mx = 0, pos = 0;
    for(int i = 0; i < n; i++){
        int d = 0, v = i;
        for(int j = lg - 1; j >= 0; j--){
            if(par[j][v] != -1 && get_sum(k, l[par[j][v]], ::r[par[j][v]] - 1) == 0){
                v = par[j][v];
                d += (1 << j);
            }
            //cout << "aha " << j << ' ' << v << ' ' << d << endl;
        }
        if(d > mx){
            mx = d;
            pos = i;
        }
        //cout << "hey " << i << ' ' << mx << endl;
    }
    return pos;

}

/*
10 6 3
4 5 6 8 2 9 7 0 1 
2 4
3 5
1 2
3 4
0 2
0 1
*/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 51668 KB Output is correct
2 Correct 22 ms 51648 KB Output is correct
3 Correct 21 ms 51672 KB Output is correct
4 Correct 21 ms 51668 KB Output is correct
5 Correct 22 ms 51656 KB Output is correct
6 Correct 20 ms 51692 KB Output is correct
7 Correct 22 ms 51668 KB Output is correct
8 Correct 22 ms 51684 KB Output is correct
9 Correct 21 ms 51668 KB Output is correct
10 Correct 21 ms 51644 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 51752 KB Output is correct
2 Correct 23 ms 52544 KB Output is correct
3 Correct 22 ms 51936 KB Output is correct
4 Correct 22 ms 52180 KB Output is correct
5 Correct 22 ms 52220 KB Output is correct
6 Correct 22 ms 51964 KB Output is correct
7 Correct 23 ms 52384 KB Output is correct
8 Correct 24 ms 52316 KB Output is correct
9 Correct 23 ms 51808 KB Output is correct
10 Correct 28 ms 52068 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 54988 KB Output is correct
2 Correct 76 ms 69140 KB Output is correct
3 Correct 38 ms 56264 KB Output is correct
4 Correct 83 ms 64752 KB Output is correct
5 Correct 84 ms 65940 KB Output is correct
6 Correct 75 ms 59684 KB Output is correct
7 Correct 74 ms 66248 KB Output is correct
8 Correct 77 ms 66508 KB Output is correct
9 Correct 36 ms 55748 KB Output is correct
10 Correct 42 ms 56192 KB Output is correct