oj.uz

Submission #871766

# Submission time Handle Problem Language Result Execution time Memory
871766 2023-11-11T14:02:15 Z LOLOLO Holiday (IOI14_holiday) C++17
100 / 100
 677 ms 18764 KB 
#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 0;

    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 (r >= st && 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 = d1[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 + 2;
        if (v + i <= d) {
            ans = max(ans, t.f + d1[d - v - i].f);
        }
    }

    for (int i = st; i >= 0; i--) {
        move(i, st);
        int v = st - i;
        if (v <= d) {
            ans = max(ans, cal(d - v));
        }
    }

    return ans;
}

/*int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int att[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 100000};
    cout << findMaxAttraction(10, 4, 7, att) << '\n';
    return 0;
}*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 836 KB Output is correct
7 Correct 0 ms 604 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 10088 KB Output is correct
2 Correct 372 ms 10088 KB Output is correct
3 Correct 427 ms 10088 KB Output is correct
4 Correct 374 ms 10068 KB Output is correct
5 Correct 434 ms 7840 KB Output is correct
6 Correct 142 ms 8796 KB Output is correct
7 Correct 227 ms 6208 KB Output is correct
8 Correct 280 ms 6176 KB Output is correct
9 Correct 92 ms 10588 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1368 KB Output is correct
2 Correct 8 ms 1116 KB Output is correct
3 Correct 11 ms 1380 KB Output is correct
4 Correct 11 ms 1116 KB Output is correct
5 Correct 10 ms 1116 KB Output is correct
6 Correct 3 ms 956 KB Output is correct
7 Correct 3 ms 860 KB Output is correct
8 Correct 3 ms 912 KB Output is correct
9 Correct 3 ms 860 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 11648 KB Output is correct
2 Correct 614 ms 18764 KB Output is correct
3 Correct 263 ms 5840 KB Output is correct
4 Correct 10 ms 1116 KB Output is correct
5 Correct 3 ms 920 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 677 ms 12876 KB Output is correct
9 Correct 675 ms 12616 KB Output is correct