Submission #1099468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099468		Zero_OP	Holiday (IOI14_holiday)	C++14	100 / 100	171 ms	39100 KiB

holiday

#include <bits/stdc++.h>
#ifndef LOCAL
    #include <holiday.h>
#endif

using namespace std;

using ll = long long;
using ld = long double;

#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true; return false;
}

const ll inf = 1e18;
const int MAXNODES = 4e6 + 5;

int lc[MAXNODES], rc[MAXNODES], cnt[MAXNODES], nNodes;
ll sum[MAXNODES];

int build(int l, int r){
    if(l == r) return ++nNodes;
    int o = ++nNodes, mid = l + r >> 1;
    lc[o] = build(l, mid);
    rc[o] = build(mid + 1, r);
    return o;
}

vector<int> values;

void refine(int cur){
    sum[cur] = sum[lc[cur]] + sum[rc[cur]];
    cnt[cur] = cnt[lc[cur]] + cnt[rc[cur]];
}

int update(int p, int l, int r, int pos){
    if(l == r){
        int o = ++nNodes;
        sum[o] = sum[p] + values[l];
        cnt[o] = cnt[p] + 1;
        return o;
    }

    int mid = l + r >> 1, o = ++nNodes;

    if(pos <= mid){
        lc[o] = update(lc[p], l, mid, pos);
        rc[o] = rc[p];
        refine(o);
    } else{
        lc[o] = lc[p];
        rc[o] = update(rc[p], mid + 1, r, pos);
        refine(o);
    }

    return o;
}

ll query(int pL, int pR, int l, int r, int k){
    if(l == r) return 1LL * values[l] * min(cnt[pR] - cnt[pL], k);
    int mid = l + r >> 1;

    int rightHave = cnt[rc[pR]] - cnt[rc[pL]]; //prioritize right first
    ll rightSum = sum[rc[pR]] - sum[rc[pL]];
    if(k > rightHave) return rightSum + query(lc[pL], lc[pR], l, mid, k - rightHave);
    else return query(rc[pL], rc[pR], mid + 1, r, k);
}

long long findMaxAttraction(int n, int start, int d, int attraction[]){
    ++start;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; ++i){
        a[i] = attraction[i - 1];
        values.push_back(a[i]);
    }

    sort(all(values));
    compact(values);

    for(int i = 1; i <= n; ++i){
        a[i] = lower_bound(all(values), a[i]) - values.begin();
    }

    int m = sz(values) - 1;


    ll ans = 0;
    auto solve = [&](){
        vector<int> roots;
        roots.push_back(build(0, m));
        for(int i = 1; i <= n; ++i){
            roots.push_back(update(roots.back(), 0, m, a[i]));
        }

        auto query_cost = [&](int l, int r){
            int moves = (r - l + min(r - start, start - l)); //choosing first direction
            if(moves > d) return -inf;
            int can_take = min(r - l + 1, d - moves);
            ll ret = query(roots[l - 1], roots[r], 0, m, can_take);
            return ret;
        };

        function<void(int, int, int, int)> dnc = [&](int l, int r, int optL, int optR){
            int mid = l + r >> 1;
            ll opt_value = -inf;
            int opt_mid = optL;

            for(int i = max(mid, optL); i <= optR; ++i){
                if(maximize(opt_value, query_cost(mid, i))){
                    opt_mid = i;
                }
            }

            ans = max(ans, opt_value);
            if(l < mid) dnc(l, mid - 1, optL, opt_mid);
            if(mid < r) dnc(mid + 1, r, opt_mid, optR);
        };

        dnc(1, start, start, n);
//        auto check_valid = [&](){
//            for(int i = 1; i <= start; ++i){
//                ll opt_value = -inf;
//                int opt_mid = -1;
//                for(int j = start; j <= n; ++j){
//                    if(maximize(opt_value, query_cost(i, j))){
//                        opt_mid = j;
//                    }
//                }
//
//                cout << opt_mid << ' ';
//            }
//            cout << '\n';
//        };
//
//        check_valid();
//        for(int i = 1; i <= start; ++i){
//            for(int j = start; j <= n; ++j){
//                maximize(ans, query_cost(i, j));
//            }
//        }
    };

    solve();
//    reverse(a.begin() + 1, a.end());
//    start = n - start + 1;
//    solve();

    return ans;
}

#ifdef LOCAL
int main(){
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
    int n, start, d;
    cin >> n >> start >> d;
    int a[n];
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }

    cout << findMaxAttraction(n, start, d, a) << '\n';
    return 0;
}
#endif

Compilation message (stderr)

holiday.cpp: In function 'bool maximize(T&, const T&)':
holiday.cpp:18:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   18 |     if(a < b) return a = b, true; return false;
      |     ^~
holiday.cpp:18:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   18 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~
holiday.cpp: In function 'int build(int, int)':
holiday.cpp:29:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int o = ++nNodes, mid = l + r >> 1;
      |                             ~~^~~
holiday.cpp: In function 'int update(int, int, int, int)':
holiday.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = l + r >> 1, o = ++nNodes;
      |               ~~^~~
holiday.cpp: In function 'll query(int, int, int, int, int)':
holiday.cpp:67:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In lambda function:
holiday.cpp:110:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |             int mid = l + r >> 1;
      |                       ~~^~~

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