Submission #795556

#	Time	Username	Problem	Language	Result	Execution time	Memory
795556		phoebe	Holiday (IOI14_holiday)	C++17	100 / 100	1183 ms	5480 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;

#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define FOR(i, n) for (int i = 0; i < n; i++)
#define PB push_back
#define ALL(x) x.begin(), x.end()
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;

const int maxn = 1e5 + 10;
int n, s, d, a[maxn], cnt[maxn * 4] = {0}, cur_l = 0, cur_r = 0;
ll tree[maxn * 4] = {0}, re = 0;
vector<int> pt;

int get(int v){
    return lower_bound(ALL(pt), v) - pt.begin();
}

int calc_dist(int l, int r){
    if (l >= s) return r - s;
    if (r <= s) return s - l;
    return r - l + min(r - s, s - l);
}

void update(int x, int delta, int tl = 0, int tr = maxn, int i = 1){
    if (tl > x || tr < x) return;
    if (tl == tr){
        tree[i] += pt[x] * delta, cnt[i] += delta; 
        return;
    }
    int tm = (tl + tr) / 2;
    update(x, delta, tl, tm, i * 2); 
    update(x, delta, tm + 1, tr, i * 2 + 1);
    tree[i] = tree[i * 2] + tree[i * 2 + 1];
    cnt[i] = cnt[i * 2] + cnt[i * 2 + 1];
}

pair<ll, int> walk(int rem, int tl = 0, int tr = maxn, int i = 1){
    // sum, cnt
    if (rem <= 0) return {0, 0};
    if (cnt[i] <= rem) return {tree[i], cnt[i]};
    if (tl == tr) return {pt[tl] * rem, rem};
    int tm = (tl + tr) / 2;
    auto right = walk(rem, tm + 1, tr, i * 2 + 1);
    auto left = walk(rem - right.S, tl, tm, i * 2);
    return {left.F + right.F, left.S + right.S};
}

ll cost(int l, int r, int rem){
    while (cur_l > l) update(get(a[--cur_l]), 1);
    while (cur_r < r) update(get(a[++cur_r]), 1);
    while (cur_l < l) update(get(a[cur_l++]), -1);
    while (cur_r > r) update(get(a[cur_r--]), -1);
    // cout << l << ' ' << r << ' ' << walk(rem).F << ' ' << walk(rem).S << ' ' << rem << endl;
    return walk(rem).F;
}

void solve(int l, int r, int opt_l, int opt_r){
    if (l > r) return;
    int r_pos = (l + r) / 2; // right end point
    ll best = 0; int opt;
    for (int l_pos = opt_l; l_pos <= min(r_pos, opt_r); l_pos++){ 
        ll val = cost(l_pos, r_pos, d - calc_dist(l_pos, r_pos));
        if (val > best) best = val, opt = l_pos;
    }
    // cout << opt << ' ' << r_pos << ' ' << best << endl;
    re = max(re, best); 
    solve(l, r_pos - 1, opt_l, opt);
    solve(r_pos + 1, r, opt, opt_r);
}

ll findMaxAttraction(int N, int start, int D, int attraction[]){
    n = N, s = start, d = D;
    for (int i = 0; i < n; i++){
        a[i] = attraction[i];
        pt.PB(a[i]);
    }
    sort(ALL(pt)); pt.resize(distance(pt.begin(), unique(ALL(pt))));
    update(get(a[0]), 1); 
    // for (auto x : tree[1]) cout << x << ' '; cout << endl;
    solve(0, n - 1, 0, n - 1);
    return re;
}

Compilation message (stderr)

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:73:10: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     solve(l, r_pos - 1, opt_l, opt);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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