제출 #718458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
718458		qwerasdfzxcl	휴가 (IOI14_holiday)	C++17	100 / 100	358 ms	53124 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"

using namespace std;
typedef long long ll;

int n, s, d, r, c, a[100100], b[100100];
ll ans;

struct Node{
    int l, r;
    ll x;
    int c;
    Node(){}
    Node(int _l, int _r, ll _x, int _c): l(_l), r(_r), x(_x), c(_c) {}
};

struct PST{
    vector<Node> tree;
    vector<int> root;
    int sz;

    ll ansx;
    int remc;

    void init(int n){
        sz = n;
        tree.clear(); root.clear();
        tree.emplace_back(0, 0, 0, 0);
        root.push_back(0);
    }
    int cp(int x){
        tree.push_back(tree[x]);
        return (int)tree.size()-1;
    }
    void update(int i, int l, int r, int p, ll x, int c){
        if (r<p || p<l) return;
        if (l==r){
            tree[i].x += x;
            tree[i].c += c;
            return;
        }

        int m = (l+r)>>1;
        if (p<=m) update(tree[i].l=cp(tree[i].l), l, m, p, x, c);
        else update(tree[i].r=cp(tree[i].r), m+1, r, p, x, c);
        tree[i].x = tree[tree[i].l].x + tree[tree[i].r].x;
        tree[i].c = tree[tree[i].l].c + tree[tree[i].r].c;
    }
    void search(int il, int ir, int l, int r){
        if (remc<=0) return;
        if (tree[ir].c - tree[il].c <= remc){
            ansx += tree[ir].x - tree[il].x;
            remc -= tree[ir].c - tree[il].c;
            return;
        }

        int m = (l+r)>>1;
        search(tree[il].r, tree[ir].r, m+1, r);
        search(tree[il].l, tree[ir].l, l, m);
    }

    void update(int p, ll x, int c){
        root.push_back(cp(root.back()));
        update(root.back(), 1, sz, p, x, c);
    }
    ll query(int l, int r, int c){
        c = max(c, 0);
        c = min(c, r-l+1);
        remc = c;
        ansx = 0;

        search(root[l-1], root[r], 1, n);
        return ansx;
    }
}tree;

ll f(int x, int y){
    return tree.query(s-x+1, s+y-1, d - (x-1)*2 - (y-1));
}

void dnc(int sx, int ex, int sy, int ey){
    if (sx > ex) return;
    
    int mid = (sx+ex)>>1;
    int opt = sy;
    ll val = f(mid, sy);
    for (int i=sy+1;i<=ey;i++){
        ll tmp = f(mid, i);
        if (tmp > val){
            val = tmp;
            opt = i;
        }
    }

    ans = max(ans, val);
    dnc(sx, mid-1, opt, ey);
    dnc(mid+1, ex, sy, opt);
}

ll solve(int N, int start, int D, int attraction[]){
    n = N, s = start+1, d = D, ans = 0;
    vector<pair<int, int>> V;
    for (int i=1;i<=n;i++){
        a[i] = attraction[i-1];
        V.emplace_back(a[i], i);
    } 

    sort(V.begin(), V.end());
    for (int i=0;i<n;i++) b[V[i].second] = i + 1;

    tree.init(n);
    for (int i=1;i<=n;i++){
        tree.update(b[i], a[i], 1);
    }

    r = s, c = n-s+1;

    dnc(1, r, 1, c);
    return ans;
}

long long int findMaxAttraction(int N, int start, int D, int attraction[]) {
    ll ans = solve(N, start, D, attraction);
    reverse(attraction, attraction+N);
    start = N - 1 - start;

    return max(ans, solve(N, start, D, attraction));
}

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