Submission #1099450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099450		Zero_OP	Holiday (IOI14_holiday)	C++14	0 / 100	76 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) << "]"

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;
            pair<ll, int> opt = {-inf, -optL};
//            cout << mid << " : " << optL << ' ' << optR << '\n';
            for(int i = max(mid, optL); i <= optR; ++i){
                opt = max(opt, {query_cost(mid, i), -i});
            }

            ans = max(ans, opt.first);
            if(l < mid) dnc(l, mid - 1, -opt.second, optR);
            if(mid < r) dnc(mid + 1, r, optL, -opt.second);
        };

        dnc(1, start, start, n);
    };

    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 constructor 'node::node(int, ll)':
holiday.cpp:21:8: warning: 'node::sum' will be initialized after [-Wreorder]
   21 |     ll sum;
      |        ^~~
holiday.cpp:19:11: warning:   'node* node::left' [-Wreorder]
   19 |     node* left, *right;
      |           ^~~~
holiday.cpp:23:5: warning:   when initialized here [-Wreorder]
   23 |     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:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'node* update(node*, int, int, int)':
holiday.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'll query(node*, node*, int, int, int)':
holiday.cpp:47:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In lambda function:
holiday.cpp:88:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |             int mid = l + r >> 1;
      |                       ~~^~~

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