Submission #602116

#	Time	Username	Problem	Language	Result	Execution time	Memory
602116		MohamedFaresNebili	Jousting tournament (IOI12_tournament)	C++14	100 / 100	85 ms	25624 KiB

tournament

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

            using namespace std;

            using ll = long long;
            using ii = pair<ll, ll>;
            using vi = vector<int>;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound

            const int oo = 1000 * 1000 * 1000 + 7;

            int ST[800005], P[200005], Pr[200005];
            vector<pair<int, int>> DP;
            vector<int> lo, hi, adj[200005];

            void build(int v, int l, int r) {
                if(l == r) {
                    ST[v] = 1;
                    return;
                }
                build(v * 2, l, (l + r) / 2);
                build(v * 2 + 1, (l + r) / 2 + 1, r);
                ST[v] = ST[v * 2] + ST[v * 2 + 1];
            }
            void update(int v, int l, int r, int p) {
                if(l == r) {
                    ST[v] = 0;
                    return;
                }
                int md = (l + r) / 2;
                if(p <= md) update(v * 2, l, md, p);
                else update(v * 2 + 1, md + 1, r, p);
                ST[v] = ST[v * 2] + ST[v * 2 + 1];
            }
            int query(int v, int l, int r, int p) {
                if(l == r) return l;
                int md = (l + r) / 2;
                if(ST[v * 2] >= p)
                    return query(v * 2, l, (l + r) / 2, p);
                return query(v * 2 + 1, (l + r) / 2 + 1, r, p - ST[v * 2]);
            }
            void dfs(int v) {
                for(auto u : adj[v]) {
                    dfs(u);
                    lo[v] = min(lo[v], lo[u]);
                    hi[v] = max(hi[v], hi[u]);
                    if(DP[u].ff > DP[v].ff)
                        DP[v] = DP[u];
                }
                if(adj[v].empty()) {
                    lo[v] = hi[v] = v;
                    DP[v] = {0, v};
                    return;
                }
                int i = hi[v] - 1, j = lo[v] - 1;
                if(j < 0) j = 0;
                if(Pr[i] - Pr[j] == 0) DP[v].ff++;
            }

            int GetBestPosition(int N, int C, int R,
                                int* K, int* S, int* E) {
                build(1, 0, N - 1); int cnt = N - 1;
                for(int l = 0; l < N; l++) P[l] = l;
                for(int i = 0; i < C; i++) {
                    int v = query(1, 0, N - 1, S[i] + 1);
                    adj[++cnt].push_back(P[v]);
                    P[v] = cnt;
                    for(int j = S[i] + 1; j <= E[i]; j++) {
                        v = query(1, 0, N - 1, S[i] + 2);
                        update(1, 0, N - 1, v);
                        adj[cnt].push_back(P[v]);
                    }
                }
                for(int l = 0; l < N - 1; l++)
                    Pr[l] = (R < K[l]);
                for(int l = 1; l < N - 1; l++)
                    Pr[l] += Pr[l - 1];
                lo.assign(2 * N, 1e9 + 7); hi.assign(2 * N, 0);
                DP.assign(2 * N, make_pair(-1, -1));
                dfs(cnt);
                return DP[cnt].ss;
            }

Compilation message (stderr)

tournament.cpp: In function 'int query(int, int, int, int)':
tournament.cpp:45:21: warning: unused variable 'md' [-Wunused-variable]
   45 |                 int md = (l + r) / 2;
      |                     ^~

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51