Submission #599991

#	Time	Username	Problem	Language	Result	Execution time	Memory
599991		MohamedFaresNebili	Meetings (IOI18_meetings)	C++14	19 / 100	444 ms	197312 KiB

meetings

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

                using namespace std;

                using ll = long long;
                using ld = long double;
                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 MOD = 1e9 + 7;

                ll N, Q, DP[5005][5005], SP[100001][20], LOG[100001];
                ll A[100005];
                struct node{
                    int val, p, s, r;
                } ST[400005];

                ll query(int i, int j) {
                    int K = LOG[j - i + 1];
                    return max(SP[i][K], SP[j - (1 << K) + 1][K]);
                }
                node merge(node U, node V) {
                    node res;
                    res.p = U.p, res.s = V.s;
                    if(U.r) res.p = U.val + V.p;
                    if(V.r) res.s = U.s + V.val;
                    res.val = max({U.val, V.val, U.s + V.p});
                    res.r = (U.r & V.r);
                    return res;
                }
                void build(int v, int l, int r) {
                    if(l == r) {
                        int x = (A[l] == 1);
                        ST[v] = {x, x, x, x};
                        return;
                    }
                    build(v * 2, l, (l + r) / 2);
                    build(v * 2 + 1, (l + r) / 2 + 1, r);
                    ST[v] = merge(ST[v * 2], ST[v * 2 + 1]);
                }
                node query(int v, int l, int r, int lo, int hi) {
                    if(l > hi || r < lo) return {-1, -1, -1, -1};
                    if(l >= lo && r <= hi) return ST[v];
                    node X = query(v * 2, l, (l + r) / 2, lo, hi);
                    node Y = query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
                    if(X.val == -1) return Y;
                    if(Y.val == -1) return X;
                    return merge(X, Y);
                }

                vector<ll> subtask(vector<int> H, vector<int> L, vector<int> R) {
                    for(int l = 0; l < N; l++)
                        A[l] = H[l];
                    build(1, 0, N - 1);
                    vector<ll> res(Q, -1);
                    for(int l = 0; l < Q; l++) {
                        int X = L[l], Y = R[l];
                        ll best = query(1, 0, N - 1, X, Y).val;
                        res[l] = best + (Y - X + 1) * 2;
                    }
                    return res;
                }

                vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
                    int M = 0; LOG[1] = 0; N = H.size(), Q = L.size();
                    for(int l = 0; l < N; l++)
                        M = max(M, H[l]);
                    if(M <= 2) return subtask(H, L, R);
                    for(int l = 2; l <= N; l++)
                        LOG[l] = LOG[l / 2] + 1;
                    for(int l = 0; l < N; l++)
                        SP[l][0] = H[l];
                    for(int l = 1; l < 20; 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++) {
                        DP[l][l] = H[l];
                        for(int i = l + 1; i < N; i++) {
                            DP[l][i] = DP[l][i - 1];
                            DP[l][i] += query(l, i);
                        }
                        for(int i = l - 1; i >= 0; i--) {
                            DP[l][i] = DP[l][i + 1];
                            DP[l][i] += query(i, l);
                        }
                    }
                    vector<ll> res(Q, -1);
                    for(int l = 0; l < Q; l++) {
                        ll best = 1000000000LL * 1LL * 1000000000LL;
                        for(int i = L[l]; i <= R[l]; i++) {
                            ll A = DP[i][R[l]];
                            if(i != L[l]) A += DP[i][L[l]] - H[i];
                            best = min(best, A);
                        }
                        res[l] = best;
                    }
                    return res;
                }

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40