제출 #1303008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303008		uranium235	휴가 (IOI14_holiday)	C++17	47 / 100	271 ms	7760 KiB

holiday

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

// ll opss[20], ops = 0;

struct node {
    int cnt;
    ll sum;
    void merge(node &l, node &r) {
        cnt = l.cnt + r.cnt;
        sum = l.sum + r.sum;
    }
};

struct segtree {
    int n;
    vector<int> comp;
    vector<node> a;
    segtree(int n, const vector<int> &i) : n(n), comp(i), a(4 * n) {
        assert(is_sorted(i.rbegin(), i.rend()));
    }
    void upd(int v, int l, int r, int i, int dx, int dy) {
        if (l == r) {
            assert(l == i);
            a[v].cnt += dx;
            a[v].sum += dy;
        } else {
            int m = (l + r) / 2;
            if (i <= m) upd(2 * v, l, m, i, dx, dy);
            else upd(2 * v + 1, m + 1, r, i, dx, dy);
            a[v].merge(a[2 * v], a[2 * v + 1]);
        }
    }
    void upd(int i, int dx, int dy) {
        i = n - 1 - (lower_bound(comp.rbegin(), comp.rend(), i) - comp.rbegin());
        upd(1, 0, n - 1, i, dx, dy);
    }
    void add(int x) {
        // ops++;
        upd(x, 1, x);
    }
    void rem(int x) {
        // ops++;
        upd(x, -1, -x);
    }
    ll walk(int v, int l, int r, int k) {
        if (l == r) {
            assert(a[v].cnt >= k);
            return ll(k) * comp[l];
        } else {
            int m = (l + r) / 2;
            if (k < a[2 * v].cnt) return walk(2 * v, l, m, k);
            else return a[2 * v].sum + walk(2 * v + 1, m + 1, r, k - a[2 * v].cnt);
        }
    }
    ll walk(int k) {
        if (k <= 0) return 0;
        if (a[1].cnt <= k) return a[1].sum;
        return walk(1, 0, n - 1, k);
    }
};

// 60
// 4436
// 334588796671
// 3389595012736
ll findMaxAttraction(int n, int start, int d, int a[]) {
    vector<int> comp;
    comp.reserve(n);
    for (int i = 0; i < n; i++) {
        comp.push_back(a[i]);
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    reverse(comp.begin(), comp.end());
    segtree tree(comp.size(), comp);

    int l = 0, r = -1;
    auto shift = [&](int ql, int qr) -> void {
        // cout << "shift (" << l << ", " << r << ") -> (" << ql << ", " << qr << ")" << endl; 
        while (l < ql) tree.rem(a[l++]);
        while (l > ql) tree.add(a[--l]);
        while (r < qr) tree.add(a[++r]);
        while (r > qr) tree.rem(a[r--]); 
    };
    int mode = 1;
    auto dnc = [&](int l, int r, int ql, int qr, auto &&self) -> ll {
        // cout << "dnc " << l << " " << r << ' ' << ql << ' ' << qr << endl;
        pair<ll, int> opt{-1, -1};
        int m = (l + r) / 2;
        assert(m <= ql);
        assert(m <= start && start <= ql);
        for (int i = ql; i <= qr; i++) {
            shift(m, i);    
            int days = (3 - mode) * (i - start) + mode * (start - m);
            // cout << "range " << ql << ' ' << m << ' ' << days << endl;
            opt = max(opt, { tree.walk(d - days), i });
        }
        // opss[depth] += ops;
        // ops = 0;
        if (l == r) return opt.first;
        else return max({ opt.first, self(l, m, ql, opt.second, self), self(m + 1, r, opt.second, qr, self) });
    };
    ll ans = dnc(0, start, start, n - 1, dnc);
    mode = 2;
    ans = max(ans, dnc(0, start, start, n - 1, dnc));
    // cout << "ops " << ops << endl;
    // for (int i = 0; i < 20; i++) {
        // cout << "layer " << i << " " << opss[i] << endl;
    // }
    // cout << "tot " << accumulate(opss, opss + 20, 0) << endl;
    return ans;
}

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