Submission #773938

#	Time	Username	Problem	Language	Result	Execution time	Memory
773938		loctildore	Holiday (IOI14_holiday)	C++14	100 / 100	1798 ms	12604 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
// trans rights
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)

struct node{
    int l, r;
    ll val;
    int cnt;
    node *lft, *rht;
    node (int tl, int tr): l(tl), r(tr), val(0), cnt(0) {
        if (l + 1 == r) {
            lft = rht = NULL;
            return;
        }
        lft = new node(l, (l + r) / 2);
        rht = new node((l + r) / 2, r);
    }

    void upd(int p, int x) {
        if (p < l || p >= r) return;
        if (l + 1 == r) {
            val += x;
            cnt = (bool) val;
            return;
        }
        lft->upd(p, x);
        rht->upd(p, x);
        val = lft->val + rht->val;
        cnt = lft->cnt + rht->cnt;
    }

    ll qry(int& x) {
        if (x <= 0) return 0;
        if (x >= cnt) {
            x -= cnt;
            return val;
        }
        ll tmp = rht->qry(x);
        return tmp + lft->qry(x);
    }
}* root;

int strt, d;
int pos[100069], val[100069];

int cl = 0, cr = 0;

bool flpd[100069];
void flp(int x) {
    if (flpd[x]) root->upd(pos[x], -val[x]);
    else root->upd(pos[x], val[x]);
    flpd[x] ^= 1;
}

void st(int tl, int tr) {
    if (tl > tr) swap(tl, tr);
    while (cl > tl) flp(--cl);
    while (cl < tl) flp(cl++);
    while (cr > tr) flp(cr--);
    while (cr < tr) flp(++cr);
}

ll fnd(int l, int r, int sl, int sr) {
    if (r < l) return 0;
    int m = (l + r) / 2;
    pair<ll, int> maxi = {INT_MIN, -1};
    for (int i = sl; i <= sr; i++) {
        st(m, i);
        int tmp = d - abs(strt - m) - abs(m - i);
        ll vl = tmp;
        if (tmp > 0) vl = root->qry(tmp); //let's hope this works
        //cout<<m<<':'<<i<<'!'<<vl<<'?'<<root->val<<endl;
        maxi = max(maxi, {vl, i});
    }
    return max(maxi.f, max(fnd(l, m - 1, sl, maxi.s), fnd(m + 1, r, maxi.s, sr)));
}

long long int findMaxAttraction(int n, int start, int D, int attraction[]) {
    strt = start; d = D;
    vector<pair<int, int>> srt;
    for (int i = 0; i < n; i++) {
        val[i] = attraction[i];
        srt.push_back({val[i], i});
    }
    sort(all(srt));
    for (int i = 0; i < n; i++) {
        pos[srt[i].s] = i;
    }

    root = new node(0, n);
    flp(0);

    return max(fnd(0, strt, 0, n - 1), fnd(strt, n - 1, 0, n - 1));
}

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