Submission #1099458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099458		Zero_OP	Holiday (IOI14_holiday)	C++14	7 / 100	71 ms	65536 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;

struct node{
    node* left, *right;
    int cnt;
    ll sum;

    node(int cnt = 0, ll sum = 0) : cnt(cnt), sum(sum), left(nullptr), right(nullptr) {}
    node(node *left, node *right) : left(left), right(right), cnt((left -> cnt) + (right -> cnt)), sum((left -> sum) + (right -> sum)) {}
};

node *build(int l, int r){
    if(l == r) return new node();
    int mid = l + r >> 1;
    return new node(build(l, mid), build(mid + 1, r));
}

vector<int> values;

node* update(node* p, int l, int r, int pos){
    if(l == r){
        return new node(p -> cnt + 1, p -> sum + values[l]);
    }

    int mid = l + r >> 1;
    if(pos <= mid) return new node(update(p -> left, l, mid, pos), p -> right);
    else return new node(p -> left, update(p -> right, mid + 1, r, pos));
}

ll query(node* pL, node* pR, int l, int r, int k){
    if(l == r) return (pR -> sum - pL -> sum);
    int mid = l + r >> 1;

    int rightHave = (pR -> right -> cnt) - (pL -> right -> cnt); //prioritize right first
    ll rightSum = (pR -> right -> sum) - (pL -> right -> sum);
    if(k > rightHave) return rightSum + query(pL -> left, pR -> left, l, mid, k - rightHave);
    else return query(pL -> right, pR -> right, 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;
    vector<node*> roots;
    roots.push_back(build(0, m));
    for(int i = 1; i <= n; ++i){
        roots.push_back(update(roots.back(), 0, m, a[i]));
    }

    ll ans = 0;
    auto solve = [&](){
        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 + 1, a + 1 + n);
    // 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 constructor 'node::node(int, ll)':
holiday.cpp:26:8: warning: 'node::sum' will be initialized after [-Wreorder]
   26 |     ll sum;
      |        ^~~
holiday.cpp:24:11: warning:   'node* node::left' [-Wreorder]
   24 |     node* left, *right;
      |           ^~~~
holiday.cpp:28:5: warning:   when initialized here [-Wreorder]
   28 |     node(int cnt = 0, ll sum = 0) : cnt(cnt), sum(sum), left(nullptr), right(nullptr) {}
      |     ^~~~
holiday.cpp: In function 'node* build(int, int)':
holiday.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'node* update(node*, int, int, int)':
holiday.cpp:45:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'll query(node*, node*, int, int, int)':
holiday.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In lambda function:
holiday.cpp:93:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |             int mid = l + r >> 1;
      |                       ~~^~~

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