Submission #601871

#	Time	Username	Problem	Language	Result	Execution time	Memory
601871		MohamedFaresNebili	Jousting tournament (IOI12_tournament)	C++14	49 / 100	443 ms	1708 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 LOG[5005], SP[5005][15];
            vector<int> P;

            int query(int i, int j) {
                int K = LOG[j - i + 1];
                return max(SP[i][K], SP[j - (1 << K) + 1][K]);
            }

            int GetBestPosition(int N, int C, int R,
                                int* K, int* S, int* E) {
                int res = 0, pos = 0; P.resize(N);
                for(int l = 0; l < N; l++) P[l] = l;
                for(int l = 0; l < C; l++) {
                    int A = lower_bound(P.begin(), P.end(), S[l]) - P.begin();
                    int B = lower_bound(P.begin(), P.end(), E[l] + 1) - P.begin() - 1;
                    for(int i = A; i <= B; i++) P[i] = P[A];
                    for(int i = B + 1; i < N; i++) P[i] -= (E[l] - S[l]);
                  	S[l] = A, E[l] = B;
                }

                LOG[1] = 0;
                for(int l = 2; l < N; l++)
                    LOG[l] = LOG[l / 2] + 1;
                for(int l = 0; l < N - 1; l++)
                    SP[l][0] = K[l];
                for(int l = 1; l < 15; l++)
                    for(int i = 0; i + (1 << l) <= N; i++)
                        SP[i][l] = max(SP[i][l - 1], SP[i + (1 << (l - 1))][l - 1]);

                for(int l = 0; l < N; l++) {
                    int best = 0;
                    for(int i = 0; i < C; i++) {
                        int lo = S[i], hi = E[i];
                        if(l > hi || l < lo) continue;
                        int A = -1, B = -1;
                        if(l > lo) A = query(S[i], l - 1);
                        if(l < hi) B = query(l, E[i] - 1);
                        A = max(A, B);
                        if(A < R) best++;
                        else break;
                    }
                    if(best > res)
                        res = best, pos = l;
                }
                return pos;
            }

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