Submission #66600

#	Time	Username	Problem	Language	Result	Execution time	Memory
66600		aquablitz11	Holiday (IOI14_holiday)	C++14	7 / 100	2750 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);
}

node *root[N];
int rev[N];
pli val[N];

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

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()
{
    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]);
    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;
    ll mxans = routine();
    if (start > 0) {
        ::start = n-start-1;
        reverse(att, att+n);
        mxans = max(mxans, routine());
    }
    return mxans;
}

Compilation message (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