제출 #882015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
882015		Pannda	휴가 (IOI14_holiday)	C++14	0 / 100	31 ms	65536 KiB

holiday

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

struct SegmentTree {
    struct Node {
        long long sum = 0;
        int cnt = 0;
        int ln = 0, rn = 0;
    };

    int n;
    vector<int> dom;
    vector<Node> nodes;

    SegmentTree(int n, vector<int> dom) : n(n), dom(dom), nodes(1) {
        nodes.reserve(n * (32 - __builtin_clz(n)));
    }

    void add(int i, int base, int &aug, int l, int r) {
        aug = nodes.size();
        nodes.push_back(nodes[base]);
        nodes[aug].cnt++;
        nodes[aug].sum += dom[i];
        if (l + 1 < r) {
            int m = (l + r) >> 1;
            if (i < m) add(i, nodes[base].ln, nodes[aug].ln, l, m);
            else add(i, nodes[base].rn, nodes[aug].rn, m, r);
        }
    }

    long long sum(int k, int idxl, int idxr, int l, int r) {
        if (l + 1 == r) {
            return 1LL * k * dom[l];
        } else {
            int m = (l + r) >> 1;
            int right_cnt = nodes[nodes[idxr].rn].cnt - nodes[nodes[idxl].rn].cnt;
            if (k >= right_cnt) {
                return sum(k - right_cnt, nodes[idxl].ln, nodes[idxr].ln, l, m) + nodes[nodes[idxr].rn].sum - nodes[nodes[idxl].rn].sum;
            } else {
                return sum(k, nodes[idxl].rn, nodes[idxr].rn, m, r);
            }
        }
    }

    void add(int i, int base, int &aug) { add(i, base, aug, 0, n); }
    long long sum(int k, int idxl, int idxr) { return sum(k, idxl, idxr, 0, n); }
};

long long findMaxAttraction(int n, int s, int d, int attraction[]) {
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = attraction[i];

    vector<int> dom = a;
    sort(dom.begin(), dom.end());
    dom.resize(unique(dom.begin(), dom.end()) - dom.begin());
    int C = dom.size();
    for (int &x : a) x = lower_bound(dom.begin(), dom.end(), x) - dom.begin();

    SegmentTree st(n, dom);
    vector<int> root(n + 1);
    root[0] = 0;
    for (int i = 0; i < n; i++) {
        st.add(a[i], root[i], root[i + 1]);
    }

    long long ans = 0;
    for (int l = 0; l <= s; l++) {
        for (int r = s + 1; r <= n; r++) {
            int distance_to_walk = min(s - l, r - s - 1) + r - l - 1;
            int playtime = d - distance_to_walk;
            if (playtime > 0) {
                ans = max(ans, st.sum(playtime, root[l], root[r]));
            }
        }
    }

    return ans;
}

//int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//
//    int n, s, d;
//    cin >> n >> s >> d;
//    int a[n];
//    for (int i = 0; i < n; i++) {
//        cin >> a[i];
//    }
//
//    cout << findMaxAttraction(n, s, d, a) << '\n';
//}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:56:9: warning: unused variable 'C' [-Wunused-variable]
   56 |     int C = dom.size();
      |         ^

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