Submission #630471

#	Time	Username	Problem	Language	Result	Execution time	Memory
630471		MohamedFaresNebili	Holiday (IOI14_holiday)	C++14	100 / 100	870 ms	17940 KiB

holiday

#include <bits/stdc++.h>
 
            using namespace std;
 
            using ll = long long;
            using ld = long double;
 
            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
 
            ll N, S, D, res;
            ll ST[400005], cur[400005];
            ll A[400005], P[400005], Pr[400005], Sf[400005];
            ll X[400005], Y[400005];
            pair<ll, ll> C[400005];
 
            void update(ll v, ll l, ll r, ll p, ll val) {
                if(l == r) {
                    ST[v] = val;
                    cur[v] = (val > 0);
                    return;
                }
                ll md = (l + r) / 2;
                if(p <= md) update(v * 2, l, (l + r) / 2, p, val);
                else update(v * 2 + 1, (l + r) / 2 + 1, r, p, val);
                ST[v] = ST[v * 2] + ST[v * 2 + 1];
                cur[v] = cur[v * 2] + cur[v * 2 + 1];
            }
            long long query(ll v, ll l, ll r, ll p) {
                if(cur[v] == p) return ST[v];
                ll md = (l + r) / 2;
                if(p <= cur[v * 2]) 
                    return query(v * 2, l, (l + r) / 2, p);
                return query(v * 2, l, (l + r) / 2, cur[v * 2])
                + query(v * 2 + 1, (l + r) / 2 + 1, r, p - cur[v * 2]);
            }
            long long query0(ll v, ll l, ll r, ll p) {
                if(cur[v] == p) return ST[v];
                ll md = (l + r) / 2;
                if(p <= cur[v * 2 + 1]) 
                    return query0(v * 2 + 1, (l + r) / 2 + 1, r, p);
                return query0(v * 2, l, (l + r) / 2, p - cur[v * 2 + 1])
                + query0(v * 2 + 1, (l + r) / 2 + 1, r, cur[v * 2 + 1]);
            }
            void solve(ll i, ll j, ll lo, ll hi) {
                if(i > j) return;
                ll md = (i + j) / 2;
                for(ll l = lo; l <= hi; l++) {
                    update(1, S, N - 1, P[l], A[l]);
                    if(md - l + S > 0) {
                        long long ans = query(1, S, N - 1, min(cur[1], md - l + S));
                        if(Pr[md] < ans) {
                            Pr[md] = ans; X[md] = l;
                        }
                    }
                }
                for(ll l = lo; l <= hi; l++)
                    update(1, S, N - 1, P[l], 0);
                solve(i, md - 1, lo, X[md]);
                solve(md + 1, j, X[md], hi);
                for(ll l = lo; l <= hi; l++)
                    update(1, S, N - 1, P[l], A[l]);
            }
            void solve0(ll i, ll j, ll lo, ll hi) {
                if(i > j) return;
                ll md = (i + j) / 2;
                for(ll l = hi; l >= lo; l--) {
                    update(1, 0, S - 1, P[l], A[l]);
                    if(md - S + 1 + l > 0) {
                        long long ans = query0(1, 0, S - 1, min(cur[1], md - S + 1 + l));
                        if(Sf[md] < ans) {
                            Sf[md] = ans; Y[md] = l;
                        }
                    }
                }
                for(ll l = lo; l <= hi; l++)
                    update(1, 0, S - 1, P[l], 0);
                solve0(i, md - 1, Y[md], hi);
                solve0(md + 1, j, lo, Y[md]);
                for(ll l = lo; l <= hi; l++)
                    update(1, 0, S - 1, P[l], A[l]);
            }
 
            long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
                N = n, S = start, D = d;
                for(ll l = 0; l < N; l++) {
                    A[l] = attraction[l];
                    C[l] = {A[l], l};
                }
                sort(C, C + start); sort(C + start, C + N);
                reverse(C + start, C + N);
                for(ll l = 0; l < N; l++)
                    P[C[l].second] = l;
                for(ll l = 0; l <= D; l++)
                    X[l] = S, Y[l] = S - 1;
                if(start < N) solve(1, D, start, N - 1);
                for(ll l = 0; l <= 4 * N; l++) ST[l] = cur[l] = 0;
                if(start > 0) solve0(1, D, 0, start - 1);
                res = max(Pr[D], Sf[D - 1]);
                for(ll l = 0; l <= D; l++) {
                    if(D - l - X[l] + S - 1 >= 0)
                        res = max(res, Pr[l] + Sf[D - l - X[l] + S - 1]);
                    if(D - l - S + Y[l] - 1 >= 0)
                        res = max(res, Sf[l] + Pr[D - l - S + Y[l] - 1]);
                }
                return res;
            }

Compilation message (stderr)

holiday.cpp: In function 'long long int query(ll, ll, ll, ll)':
holiday.cpp:34:20: warning: unused variable 'md' [-Wunused-variable]
   34 |                 ll md = (l + r) / 2;
      |                    ^~
holiday.cpp: In function 'long long int query0(ll, ll, ll, ll)':
holiday.cpp:42:20: warning: unused variable 'md' [-Wunused-variable]
   42 |                 ll md = (l + r) / 2;
      |                    ^~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53