Submission #292167

#	Time	Username	Problem	Language	Result	Execution time	Memory
292167		stoyan_malinin	Holiday (IOI14_holiday)	C++14	47 / 100	5097 ms	34936 KiB

holiday

#include "holiday.h"
//#include "grader.cpp"

#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <cstring>
#include <assert.h>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

const int MAXN = 1e5 + 5;

struct SegmentTree
{
    int cnt;
    long long sum;
    SegmentTree *L, *R;

    void build(int l, int r)
    {
        cnt = sum = 0;
        if(l==r) return;

        L = new SegmentTree();
        R = new SegmentTree();

        L->build(l, (l+r)/2);
        R->build((l+r)/2+1, r);
    }

    void update(int q, int cntChange, int sumChange, int l, int r, SegmentTree *other)
    {
        cnt = other->cnt;
        sum = other->sum;

        if(l==r)
        {
            cnt += cntChange;
            sum += sumChange;
            return;
        }

        if(l<=q && q<=(l+r)/2)
        {
            L = new SegmentTree();
            L->update(q, cntChange, sumChange, l, (l+r)/2, other->L);
        }
        else
        {
            L = other->L;
        }

        if((l+r)/2+1<=q && q<=r)
        {
            R = new SegmentTree();
            R->update(q, cntChange, sumChange, (l+r)/2+1, r, other->R);
        }
        else
        {
            R = other->R;
        }

        cnt = L->cnt + R->cnt;
        sum = L->sum + R->sum;
    }

    long long getTop(int getCnt, int l, int r)
    {
        if(sum==0) return 0;
        if(getCnt==0) return 0;
        if(getCnt>=cnt) return sum;
        if(l==r) return min(getCnt, cnt)*(sum/cnt);

        if(R->cnt<=getCnt) return R->sum + L->getTop(getCnt-R->cnt, l, (l+r)/2);
        return R->getTop(getCnt, (l+r)/2+1, r);
    }
};

SegmentTree *base;
map <int, int> numCode;

SegmentTree *T[MAXN];

void init(int *a, int n, int start)
{
    set <int> s;
    for(int i = 0;i<n;i++)
        s.insert(a[i]);

    int ind = 0;
    for(int x: s)
    {
        numCode[x] = ind;
        ind++;
    }

    base = new SegmentTree();
    base->build(0, numCode.size()-1);

    //T[start] = new SegmentTree();
    //T[start]->update(numCode[ a[start] ], 1, a[start], 0, numCode.size()-1, base);

    T[start] = base;
    for(int i = start-1;i>=0;i--)
    {
        T[i] = new SegmentTree();
        T[i]->update(numCode[ a[i] ], 1, a[i], 0, numCode.size()-1, T[i+1]);
    }
    for(int i = start+1;i<n;i++)
    {
        T[i] = new SegmentTree();
        T[i]->update(numCode[ a[i] ], 1, a[i], 0, numCode.size()-1, T[i-1]);
    }
}

long long evalSegment(int start, int finish, int d)
{
    d -= abs(start-finish);
    return T[finish]->getTop(d, 0, numCode.size()-1);
}

long long solve1(int n, int start, int d)
{
    long long answer = 0;
    int lastLOpt = start, lastROpt = n - 1;

    for(int dLeft = 0;dLeft<=min(d, start*3);dLeft++)
    {
        int opt = start;

        long long currL = 0;
        for(int l = start-1;l>=0;l--)
        {
            if((start-l)*2>dLeft) break;

            long long val = evalSegment(start, l, dLeft-(start-l));
            if(currL<val)
            {
                currL = val;
                opt = l;
            }
        }
        assert(opt<=lastLOpt);
        lastLOpt = opt;

        opt = start;

        long long currR = 0;
        int dRight = d - dLeft;
        for(int r = start+1;r<n;r++)
        {
            if(r-start>dRight) break;

            long long val = evalSegment(start, r, dRight);
            if(currR<val)
            {
                currR = val;
                opt = r;
            }
        }
        assert(opt<=lastROpt);
        lastROpt = opt;

        answer = max(answer, currL + currR);
    }

    return answer;
}

long long solve2(int n, int start, int d)
{
    long long answer = 0;
    for(int dLeft = 0;dLeft<=min(d, start*3);dLeft++)
    {
        long long currL = 0;
        for(int l = start-1;l>=0;l--)
        {
            if((start-l)>dLeft) break;
            currL = max(currL, evalSegment(start, l, dLeft));
        }

        long long currR = 0;
        int dRight = d - dLeft;
        for(int r = start+1;r<n;r++)
        {
            if((r-start)*2>dRight) break;
            currR = max(currR, evalSegment(start, r, dRight-(r-start)));
        }

        answer = max(answer, currL + currR);
    }

    return answer;
}

long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
    init(attraction, n, start);

    long long answer = 0;

    answer = max(answer, solve1(n, start, d));
    answer = max(answer, solve1(n, start, d-1) + attraction[start]);

    answer = max(answer, solve2(n, start, d));
    answer = max(answer, solve2(n, start, d-1) + attraction[start]);

    return answer;
}

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