oj.uz

Submission #602116

# Submission time Handle Problem Language Result Execution time Memory
602116 2022-07-22T15:05:17 Z MohamedFaresNebili Jousting tournament (IOI12_tournament) C++14
100 / 100
 85 ms 25624 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Correct 5 ms 5008 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 4 ms 5004 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5016 KB Output is correct
2 Correct 5 ms 5972 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 10 ms 5588 KB Output is correct
5 Correct 6 ms 5656 KB Output is correct
6 Correct 9 ms 5456 KB Output is correct
7 Correct 9 ms 5808 KB Output is correct
8 Correct 6 ms 5652 KB Output is correct
9 Correct 6 ms 5344 KB Output is correct
10 Correct 7 ms 5488 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 9496 KB Output is correct
2 Correct 85 ms 25624 KB Output is correct
3 Correct 36 ms 11668 KB Output is correct
4 Correct 81 ms 19576 KB Output is correct
5 Correct 73 ms 21400 KB Output is correct
6 Correct 84 ms 14136 KB Output is correct
7 Correct 73 ms 21552 KB Output is correct
8 Correct 82 ms 21616 KB Output is correct
9 Correct 36 ms 11300 KB Output is correct
10 Correct 50 ms 11688 KB Output is correct