Submission #1227924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227924		nh0902	휴가 (IOI14_holiday)	C++20	100 / 100	244 ms	5068 KiB

holiday

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

const int N = 1e5 + 10;

const int M = 3e5 + 10;

const int inf = 1e9;

const int mod = 1e9 + 7;

int n, start, d, a[N], order[N];

// segment tree

long long st[4 * N];
int st_cnt[4 * N];

void update(int id, int l, int r, int p, int cnt, long long val) {

    st_cnt[id] += cnt;
    st[id] += val;

    if (l == r) return;

    int mid = (l + r) / 2;
    if (p <= mid) update(id * 2, l, mid, p, cnt, val);
    else update(id * 2 + 1, mid + 1, r, p, cnt, val);
}

void add(int i) {
    update(1, 1, n, order[i], 1, a[i]);
}

void del(int i) {
    update(1, 1, n, order[i], - 1, - a[i]);
}

long long get(int id, int k) {
    if (k <= 0) return 0;

    if (st_cnt[id] <= k) return st[id];

    return get(id * 2 + 1, k) + get(id * 2, k - st_cnt[id * 2 + 1]) ;
}

bool cmp(int i, int j) {
    return a[i] < a[j];
}

int dis(int l, int r) {
    if (l > r) return 0;
    if (start <= l) return r - start;
    if (r <= start) return start - l;
    return r - l + min(start - l, r - start);
}

int cur_l = 1, cur_r = 0;

long long sum(int l, int r, int k) {
    if (r < cur_l || cur_r < l) {
        for (int i = cur_l; i <= cur_r; i ++) del(i);
        for (int i = l; i <= r; i ++) add(i);
    } else {
        if (cur_l <= l) {
            for (int i = cur_l; i < l; i ++) del(i);
        } else {
            for (int i = l; i < cur_l; i ++) add(i);
        }

        if (r <= cur_r) {
            for (int i = r + 1; i <= cur_r; i ++) del(i);
        } else {
            for (int i = cur_r + 1; i <= r; i ++) add(i);
        }
    }

    cur_l = l;
    cur_r = r;

    return get(1, k);
}

long long ans = 0;

void dvc(int l, int r, int x, int y) {

    if (l > r) return;

    int m = (l + r) / 2;

    long long best_sum = 0;
    int best = - 1;

    for (int i = x; i <= y; i ++) {
        long long cur = sum(m, i, d - dis(m, i));
        if (cur > best_sum) {
            best_sum = cur;
            best = i;
        }
    }

    //cout << m << " : " << best << " " << best_sum << "\n";

    ans = max(ans, best_sum);

    dvc(l, m - 1, x, best);
    dvc(m + 1, r, best, y);
}

long long int findMaxAttraction(int _n, int _start, int _d, int *attraction) {
    n = _n;
    start = _start + 1;
    d = _d;
    int pos[n + 1];
    for (int i = 1; i <= n; i ++) {
        a[i] = attraction[i - 1];
        pos[i] = i;
    }
    sort(pos + 1, pos + 1 + n, cmp);
    for (int i = 1; i <= n; i ++) order[pos[i]] = i;

    dvc(1, start, start, n);

    return ans;
}

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