Submission #155888

#	Time	Username	Problem	Language	Result	Execution time	Memory
155888		Alexa2001	Holiday (IOI14_holiday)	C++17	24 / 100	115 ms	65540 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#define mid ((st+dr)>>1)

using namespace std;

typedef long long ll;

const ll inf = 1e18;
const int Nmax = 1e5 + 5;
const int lim = 1e9;

ll ans[Nmax];
int best[Nmax];
int T, K;

struct Node
{
    Node *left, *right;
    ll sum; int sz;

    Node()
    {
        left = right = NULL;
        sum = 0;
        sz = 0;
    }

    Node(Node *_left, Node *_right, ll _sum, int _sz)
    {
        left = _left; right = _right;
        sum = _sum; sz = _sz;
    }

    Node(Node *_left, Node *_right)
    {
        left = _left; right = _right;
        sum = (left ? left->sum : 0) + (right ? right->sum : 0);
        sz = (left ? left->sz : 0) + (right ? right->sz : 0);
    }

    Node* update(int st, int dr, int pos)
    {
        if(st == dr)
            return new Node(left, right, sum + pos, sz + 1);

        if(pos <= mid)
        {
            if(!left) left = new Node();
            return new Node( left->update(st, mid, pos), right );
        }
        else
        {
            if(!right) right = new Node();
            return new Node( left, right->update(mid+1, dr, pos) );
        }
    }
} *aint[Nmax];


ll query(int st, int dr, Node *a, Node *b, int k)
{
    if(k < 0) return -inf;
    if(k > b->sz - a->sz) return b->sum - a->sum;
    if(st == dr) return (ll) k * st;

    ll sum = 0; int nr = 0;

    if(!a->left) a->left = new Node();
    if(!a->right) a->right = new Node();
    if(!b->left) b->left = new Node();
    if(!b->right) b->right = new Node();

    sum += b->right->sum, nr += b->right->sz;
    sum -= a->right->sum, nr -= a->right->sz;

    if(nr >= k) return query(mid+1, dr, a->right, b->right, k);
        else return sum + query(st, mid, a->left, b->left, k - nr);
}

void divide(int st, int dr, int L, int R)
{
    ans[mid] = -inf; best[mid] = -1;

    int i;
    for(i=L; i<=R; ++i)
    {
        int rest = T - 2 * (K - mid) - (i - K);

        ll res = query(0, lim, aint[mid], aint[i+1], rest);

        if(res > ans[mid])
            ans[mid] = res, best[mid] = i;
    }

    if(st <= mid-1) divide(st, mid-1, L, best[mid]);
    if(mid+1 <= dr) divide(mid+1, dr, best[mid], R);
}

ll solve(int N, int _K, int _T, int A[])
{
    K = _K; T = _T;

    int i;

    aint[0] = new Node();
    for(i=1; i<=N; ++i)
    {
        aint[i] = aint[i-1];
        aint[i] = aint[i] -> update(0, lim, A[i-1]);
    }

    divide(0, K, K, N-1);

    ll Ans = 0;
    for(i=0; i<N; ++i) Ans = max(Ans, ans[i]);
    return Ans;
}

ll findMaxAttraction(int n, int start, int days, int A[])
{
    int i, *B;
    B = new int[n];
    for(i=0; i<n; ++i) B[i] = A[n-1-i];

    return max( solve(n, start, days, A), solve(n, n-1-start, days, B) );
}

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