제출 #285762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285762		Kastanda	휴가 (IOI14_holiday)	C++11	100 / 100	815 ms	7536 KiB

holiday

// M
#include<bits/stdc++.h>
#include"holiday.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int N = 100005;
int n, st, d, A[N], Id[N], C[N * 4];
ll SM[N * 4];
vector < int > U;
ll MX;
void AddSeg(int i, int val, int id = 1, int l = 0, int r = (int)U.size())
{
        C[id] += val;
        SM[id] += (ll)val * U[i];
        if (r - l < 2)
                return ;
        if (i < md)
                AddSeg(i, val, lc, l, md);
        else
                AddSeg(i, val, rc, md, r);
}
ll GetSeg(int &k, int id = 1, int l = 0, int r = (int)U.size())
{
        if (k <= 0)
                return 0LL;
        if (C[id] <= k)
                return k -= C[id], SM[id];
        if (r - l < 2)
        {
                ll rt = (ll)U[l] * k;
                k = 0;
                return rt;
        }
        ll rt = GetSeg(k, rc, md, r);
        rt += GetSeg(k, lc, l, md);
        return rt;
}
inline void Add(int i, int val)
{
        AddSeg(Id[i], val);
}
ll Get(int k)
{
        int kk = k;
        return GetSeg(kk);
}
void Solve(int l, int r, int le, int ri)
{
        if (r < l)
                return ;
        int opt = -1;
        // [le, l) is added.
        for (int i = l; i <= md; i ++)
                Add(i, 1);
        ll Mx = 0;
        for (int i = le; i <= ri; i ++)
        {
                ll val = Get(d - (md - st + md - i));
                if (Mx <= val)
                        Mx = val, opt = i;
                Add(i, -1);
        }
        MX = max(MX, Mx);
        // (ri, md]
        for (int i = opt; i <= ri; i ++)
                Add(i, 1);
        // [opt, md]
        Solve(md + 1, r, opt, ri);
        for (int i = le; i < opt; i ++)
                Add(i, 1);
        // [le, md]
        for (int i = l; i <= md; i ++)
                Add(i, -1);
        // [le, l)
        Solve(l, md - 1, le, opt);
}

ll findMaxAttraction(int _n, int _start, int _d, int attraction[])
{
        n = _n; st = _start; d = _d;
        for (int i = 0; i < n; i ++)
                A[i] = attraction[i], U.push_back(A[i]);

        sort(U.begin(), U.end());
        U.resize(unique(U.begin(), U.end()) - U.begin());
        for (int i = 0; i < n; i ++)
                Id[i] = lower_bound(U.begin(), U.end(), A[i]) - U.begin();
        MX = 0;
        for (int w = 0; w <= 1; w ++)
        {
                memset(C, 0, sizeof(C));
                memset(SM, 0, sizeof(SM));
                for (int i = st; i < n; i ++)
                        Add(i, 1), MX = max(MX, Get(d - (i - st)));
                memset(C, 0, sizeof(C));
                memset(SM, 0, sizeof(SM));
                // Adding [le, l) :
                for (int i = 0; i < st; i ++)
                        Add(i, 1);
                Solve(st, n - 1, 0, st - 1);
                reverse(A, A + n);
                reverse(Id, Id + n);
                st = n - 1 - st;
        }
        return MX;
}

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