제출 #66601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66601		aquablitz11	휴가 (IOI14_holiday)	C++14	7 / 100	2409 ms	66560 KiB

holiday

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

const int N = 100010;

int n, start, od, *att;

struct node {
    int cnt;
    ll sum;
    node *l, *r;
    node(int c, ll x) : cnt(c), sum(x), l(0), r(0) {}
    node(node *l, node *r) : l(l), r(r), cnt(l->cnt+r->cnt), sum(l->sum+r->sum) {}
};

node *build(int b=0, int e=n-1) {
    if (b == e) return new node(0, 0);
    int m = (b+e)/2;
    return new node(build(b, m), build(m+1, e));
}

node *update(int i, ll x, node *p, int b=0, int e=n-1) {
    if (b == e) return new node(1, x);
    int m = (b+e)/2;
    if (i <= m) return new node(update(i, x, p->l, b, m), p->r);
    else return new node(p->l, update(i, x, p->r, m+1, e));
}

ll query(int l, int r, node *p, int b=0, int e=n-1) {
    if (b >= l && e <= r) return p->sum;
    if (b > r || e < l) return 0;
    int m = (b+e)/2;
    return query(l, r, p->l, b, m) + query(l, r, p->r, m+1, e);
}

int bsearch(ll c, node *pl, node *pr, int b=0, int e=n-1) {
    if (b == e) return b;
    int m = (b+e)/2;
    int lcnt = pr->l->cnt - pl->l->cnt;
    if (lcnt >= c)
        return bsearch(c, pl->l, pr->l, b, m);
    else
        return bsearch(c-lcnt, pl->r, pr->r, m+1, e);
}

bool inrev = false;
node *root[N];
int rev[N];
pli val[N];

inline ll topk(int l, int r, int k)
{
    if (inrev) {
        l = n-l-1;
        r = n-r-1;
        swap(l, r);
    }
    int i = bsearch(k, root[l], root[r+1]);
    ll sum = query(0, i, root[r+1]) - query(0, i, root[l]);
    return sum;
}

inline pli solve(int s, int al, int ar)
{
    int d = od-(start-s);
    pli ans(0, -1);
    for (int i = max(s, al); i <= ar; ++i) {
        int num = d-(i-s);
        if (num <= 0) break;
        ans = max(ans, pli(topk(s, i, num), i));
    }
    return ans;
}

ll dncopt(int b, int e, int al, int ar)
{
    if (b > e) return 0;
    int m = (b+e)/2;
    pli ans = solve(m, al, ar);
    ll q1 = dncopt(b, m-1, al, ans.second);
    ll q2 = dncopt(m+1, e, ans.second, ar);
    return max(ans.first, max(q1, q2));
}

ll routine()
{
    return dncopt(0, start, 0, n-1);
}

ll findMaxAttraction(int n, int start, int d, int att[])
{
    ::n = n, ::start = start, ::od = d, ::att = att;

    for (int i = 0; i < n; ++i)
        val[i] = pli(att[i], i);
    sort(val, val+n, greater<pli>());
    for (int i = 0; i < n; ++i)
        rev[val[i].second] = i;
    root[0] = build();
    for (int i = 0; i < n; ++i)
        root[i+1] = update(rev[i], att[i], root[i]);

    ll mxans = routine();
    if (start > 0) {
        inrev = true;
        ::start = n-start-1;
        reverse(att, att+n);
        mxans = max(mxans, routine());
    }
    return mxans;
}

/*int main() {
    int n, start, d;
    int attraction[100000];
    int i, n_s;
    n_s = scanf("%d %d %d", &n, &start, &d);
    for (i = 0 ; i < n; ++i) {
	n_s = scanf("%d", &attraction[i]);
    }
    printf("%lld\n", findMaxAttraction(n, start, d,  attraction));
    return 0;
}*/

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

holiday.cpp: In constructor 'node::node(node*, node*)':
holiday.cpp:14:15: warning: 'node::r' will be initialized after [-Wreorder]
     node *l, *r;
               ^
holiday.cpp:12:9: warning:   'int node::cnt' [-Wreorder]
     int cnt;
         ^~~
holiday.cpp:16:5: warning:   when initialized here [-Wreorder]
     node(node *l, node *r) : l(l), r(r), cnt(l->cnt+r->cnt), sum(l->sum+r->sum) {}
     ^~~~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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