Submission #578202

#	Time	Username	Problem	Language	Result	Execution time	Memory
578202		SlavicG	Holiday (IOI14_holiday)	C++17	100 / 100	1515 ms	15956 KiB

holiday

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

#define ll long long

const int N = 2e5 + 10;
ll c[N], sum[4 * N], cnt[4 * N], lazy[4 * N], pos[N], bruh, ccc[N];
pair<ll, ll> rr[5 * N], lll[5 * N];

ll query(int i, int l, int r, int k) {
    if(l > r || k <= 0) return 0;
    if(cnt[i] <= k) return sum[i];
    int mid = l + r >> 1;
    if(cnt[2 * i] > k) return query(2 * i, l, mid, k);
    return sum[2 * i] + query(2 * i + 1, mid + 1, r, k - cnt[2 * i]);
}

void modif(int i, int l, int r, int pos, bool b) {
    if(l > pos || r < pos) return;
    if(l == pos && r == pos) {
        sum[i] = (b ? c[l] : 0);
        cnt[i] = b;
        return;
    }
    int mid = l + r >> 1;
    modif(2 * i, l, mid, pos, b);
    modif(2 * i + 1, mid + 1, r, pos, b);
    sum[i] = sum[2 * i] + sum[2 * i + 1];
    cnt[i] = cnt[2 * i] + cnt[2 * i + 1];
}

int L, R;
void move_pointers(int l, int r) {
    while(L > l) {
        --L;
        ++ccc[L];
        if(ccc[L] == 1) modif(1, 0, N - 1, pos[L], 1);
    }
    while(L < l) {
        if(ccc[L] == 1) modif(1, 0, N - 1, pos[L], 0);
        --ccc[L];
        ++L;
    }

    while(R < r) {
        ++R;
        ++ccc[R];
        if(ccc[R] == 1) modif(1, 0, N - 1, pos[R], 1);
    }
    while(R > r) {
        if(ccc[R] == 1) modif(1, 0, N - 1, pos[R], 0);
        --ccc[R];
        --R;
    }
}

void rec_right(int dl, int dr, int l, int r, int start) {
    if(l > r || dl > dr) return;
    ll ans = 0, idx = l;
    int d = ((dl + dr) >> 1) - abs(l - start);
    for(int i = l; i <= r && d >= 0; ++i) {
        move_pointers(start, i);
        if(ans < query(1, 0, N - 1, d)) {
            ans = query(1, 0, N - 1, d);
            idx = i;
        }
        --d;
    }

    d = (dl + dr) >> 1;
    rr[d] = {ans, idx};
    if(dl == dr) return;
    rec_right(dl, d - 1, l, idx, start);
    rec_right(d + 1, dr, idx, r, start);
}

void rec_left(int dl, int dr, int l, int r, int start) {
    if(l > r || dl > dr) return;
    ll ans = 0, idx = r;
    int d = ((dl + dr) >> 1) - abs(r - start);
    for(int i = r; i >= l && d >= 0; --i) {
        move_pointers(i, start);
        if(ans < query(1, 0, N - 1, d)) {
            ans = query(1, 0, N - 1, d);
            idx = i;
        }
        --d;
    }

    d = (dl + dr) >> 1;
    lll[d] = {ans, idx};
    if(dl == dr) return;
    rec_left(dl, d - 1, idx, r, start);
    rec_left(d + 1, dr, l, idx, start);
}

long long int findMaxAttraction(int n, int start, int d, int a[]) {
    bruh = n;
    vector<pair<int, int>> x;
    for(int i = 0; i < n; ++i) x.push_back({a[i], i});
    sort(x.rbegin(), x.rend());
    for(int i = 0; i < n; ++i) {
        c[i] = x[i].first;
        pos[x[i].second] = i;
    }

    L = 0, R = n - 1;
    for(int i = 0; i < n; ++i) {
        ccc[i] = 1;
        modif(1, 0, N - 1, pos[i], 1);
    }
    rec_right(0, d, start, n - 1, start);
    if(start == 0) return rr[d].first;
    if(start == n - 1) {
        rec_left(0, d, 0, start, start);
        return lll[d].first;
    }
    ll ans = rr[d].first;

    L = 0, R = n - 1;
    for(int i = 0; i < n; ++i) {
        ccc[i] = 1;
        modif(1, 0, N - 1, pos[i], 1);
    }
    rec_left(0, d, 0, start - 1, start - 1);

    for(int dd = 0; dd <= d; ++dd) {
        pair<ll, ll> p = rr[dd];
        ll cur = p.first;
        ans = max(ans, cur);
        ll rem = d - dd - abs(p.second - (start - 1));
        if(rem >= 0) {
            ans = max(ans, cur + lll[rem].first);
        }
    }

    L = 0, R = n - 1;
    for(int i = 0; i < n; ++i) {
        ccc[i] = 1;
        modif(1, 0, N - 1, pos[i], 1);
    }
    rec_left(0, d, 0, start, start);

    ans = max(ans, lll[d].first);

    L = 0, R = n - 1;
    for(int i = 0; i < n; ++i) {
        ccc[i] = 1;
        modif(1, 0, N - 1, pos[i], 1);
    }
    rec_right(0, d, start + 1, n - 1, start + 1);

    for(int dd = 0; dd <= d; ++dd) {
        pair<ll, ll> p = lll[dd];
        ll cur = p.first;
        ans = max(ans, cur);
        ll rem = d - dd - abs((start + 1) - p.second);
        if(rem >= 0) {
            ans = max(ans, cur + rr[rem].first);
        }
    }
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'long long int query(int, int, int, int)':
holiday.cpp:14:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |     int mid = l + r >> 1;
      |               ~~^~~
holiday.cpp: In function 'void modif(int, int, int, int, bool)':
holiday.cpp:26:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int mid = l + r >> 1;
      |               ~~^~~

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