Submission #871762

#	Time	Username	Problem	Language	Result	Execution time	Memory
871762		LOLOLO	Holiday (IOI14_holiday)	C++17	23 / 100	592 ms	19312 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 4e6 + 100;

pair <ll, ll> seg[N];
int n;

void upd(int id, int l, int r, int x, int v, int add) {
    if (l > x || r < x)
        return;

    if (l == r) {
        seg[id].f += v;
        seg[id].s += add;
        return;
    }

    int m = (l + r) / 2;
    upd(id * 2, l, m, x, v, add);
    upd(id * 2 + 1, m + 1, r, x, v, add);
    seg[id].f = seg[id * 2].f + seg[id * 2 + 1].f;
    seg[id].s = seg[id * 2].s + seg[id * 2 + 1].s;
}    

ll get(int id, int l, int r, ll cnt) {
    if (seg[id].f <= cnt)
        return seg[id].s;

    if (l == r) {
        return min((seg[id].s / seg[id].f) * cnt, seg[id].s);
    }

    int m = (l + r) / 2;

    if (seg[id * 2 + 1].f >= cnt)
        return get(id * 2 + 1, m + 1, r, cnt);

    return get(id * 2, l, m, cnt - seg[id * 2 + 1].f) + seg[id * 2 + 1].s;
}

int L, R;
vector <int> v, rnk;

void move(int l, int r) {
    while (L < l) {
        upd(1, 0, n - 1, rnk[L], -1, -v[L]);
        L++;
    }

    while (L > l) {
        L--;
        upd(1, 0, n - 1, rnk[L], 1, v[L]);
    }

    while (R < r) {
        R++;
        upd(1, 0, n - 1, rnk[R], 1, v[R]);
    }

    while (R > r) {
        upd(1, 0, n - 1, rnk[R], -1, -v[R]);
        R--;
    }
}

ll cal(int v) {
    if (v < 0)
        return -1;

    return get(1, 1, n, v);
}

void maximize(pair <ll, ll> &a, pair <ll, ll> b) {
    if (a.f < b.f) {
        a = b;
    } else {
        if (a.f == b.f) {
            a.s = min(a.s, b.s);
        }
    }
}

void dnc(int st, int l1, int r1, int l, int r, vector <pair <ll, ll>> &f) {
    if (l1 > r1 || st < 0)
        return;

    int m1 = (l1 + r1) / 2;
    
    for (int i = l; i <= r; i++) {
        move(min(st, i), max(st, i));
        ll v = cal(m1 - abs(i - st));
        maximize(f[m1], {v, abs(i - st)});
    }

    int opt = f[m1].s;

    if (l >= st) {
        dnc(st, l1, m1 - 1, l, opt + st, f);
        dnc(st, m1 + 1, r1, opt + st, r, f);
    } else {
        dnc(st, m1 + 1, r1, l, st - opt, f);
        dnc(st, l1, m1 - 1, st - opt, r, f);
    }
}

ll findMaxAttraction(int _n, int st, int d, int att[]) {
    n = _n;
    map <int, int> mp;
    int timer = 0;
    for (int i = 0; i < n; i++) {
        v.pb(att[i]);
        mp[att[i]];
    }

    for (auto &x : mp) {
        x.s = timer;
        timer++;
    }

    for (auto x : v)
        rnk.pb(mp[x]);

    L = R = 0;
    upd(1, 0, n - 1, rnk[L], 1, v[L]);

    vector <pair <ll, ll>> d1(d + 1, {0, 0}), d2(d + 1, {0, 0});
    dnc(st, 0, d, st, n - 1, d1);
    dnc(st - 1, 0, d, 0, st - 1, d2);

    ll ans = max(d1[d].f, d2[d].f);

    for (int i = 0; i < d; i++) {
        auto t = d1[i];
        int v = t.s + 1;
        if (v + i <= d) {
            ans = max(ans, t.f + d2[d - v - i].f);
        }

        t = d2[i];
        v = t.s + 1;
        if (v + i <= d) {
            ans = max(ans, t.f + d1[d - v - i].f);
        }
    }

    return ans;
}

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