Submission #242517

#	Time	Username	Problem	Language	Result	Execution time	Memory
242517		joseacaz	Holiday (IOI14_holiday)	C++17	0 / 100	1480 ms	17180 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

struct Node
{
    ll val = 0, active = 0;
    Node() { val = 0, active = 0; }
    Node(ll _v, ll _a) { val = _v; active = _a; }
    
    Node operator+ (const Node& _x) const
    {
        return {val + _x.val, active + _x.active};
    }
};

const int MAXN = 1e5 + 5;
int N, a[MAXN], pos[MAXN], D;
pll b[MAXN];
Node ST[4*MAXN];

bool cmp(pll _a, pll _b)
{
    if(_a.first == _b.first)
        return _a.second < _b.second;
    return _a.first > _b.first;
}

void upd(int pos, int x, int node = 0, int l = 0, int r = N - 1)
{
    if(r < pos || pos < l)
        return;
    if(l == r)
    {
        if(x)
            ST[node].val = b[l].first;
        else
            ST[node].val = 0;
        ST[node].active = x;
        return;
    }
    
    int mid = (l+r)/2, lchild = 2*node + 1, rchild = 2*node + 2;
    upd(pos, x, lchild, l, mid);
    upd(pos, x, rchild, mid + 1, r);
    ST[node] = ST[lchild] + ST[rchild];
}

ll qry(int x, int node = 0, int l = 0, int r = N - 1)
{
    if(x < 0)
        return -(1LL << 60LL);
    if(x == 0)
        return 0;
    if(l == r)
        return ST[node].val;

    int mid = (l+r)/2, lchild = 2*node + 1, rchild = 2*node + 2;
    if(ST[lchild].active <= x)
        return ST[lchild].val + qry(x - ST[lchild].active, rchild, mid + 1, r);
    else
        return qry(x, lchild, l, mid);
}

int start;
pll f[3*MAXN], g[3*MAXN];

void solve(int l, int r, int l1, int r1)
{
    if(l1 > r1)
        return;
    int days = (l1 + r1)/2;
    for(int i = l; i <= r; i++)
        upd(pos[i], 0);
    ll maxim = 0, tmp = l;
    for(int i = l; i <= r; i++)
    {
        if(days-i+start+1 < 0)
            break;
        upd(pos[i], 1);
        ll aux = qry(days-i+start+1);
        if(aux > maxim)
        {
            maxim = aux;
            tmp = i;
        }
    }
    f[days] = {tmp, maxim};
    for(int i = l; i <= r; i++)
        upd(pos[i], 0);
    solve(l, f[days].first, l1, days - 1);
    for(int i = l; i < f[days].first; i++)
        upd(pos[i], 1);
    solve(f[days].first, r, days + 1, r1);
}

void solve2(int l, int r, int l1, int r1)
{
    if(l1 > r1)
        return;
    int days = (l1 + r1)/2;
    for(int i = r; i >= l; i--)
        upd(pos[i], 0);
    ll maxim = 0, tmp = r;
    for(int i = r; i >= l; i--)
    {
        if(days-start+1+i < 0)
            break;
        upd(pos[i], 1);
        ll aux = qry(days-start+1+i);
        if(aux > maxim)
        {
            maxim = aux;
            tmp = i;
        }
    }
    g[days] = {tmp, maxim};
    for(int i = r; i >= l; i--)
        upd(pos[i], 0);
    solve2(g[days].first, r, l1, days - 1);
    for(int i = g[days].first + 1; i <= r; i++)
        upd(pos[i], 1);
    solve2(l, g[days].first, days + 1, r1);
}

ll findMaxAttraction(int _n, int _start, int _d, int att[])
{
    N = _n;
    D = _d;
    start = _start;
    for(int i = 0; i < N; i++)
    {
        a[i] = att[i];
        b[i] = {att[i], i};
    }
    sort(b, b + N, cmp);
    for(int i = 0; i < N; i++)
        pos[b[i].second] = i;
    
    for(int i = 0; i < N; i++)
        upd(i, 0);
    solve(start + 1, N - 1, 0, D);
    for(int i = 0; i < N; i++)
        upd(i, 0);
    solve2(0, start - 1, 0, D);

    if(!D)
        return 0;
    ll ans = a[start];
    for(int i = 0; i <= D; i++)
    {
        if(D - i - 2 - f[i].first - start >= 0)
            ans = max(ans, g[D - i - 2 - f[i].first - start].second + f[i].second);
        if(D - i - 2 - start + g[i].first >= 0)
            ans = max(ans, f[D - i - 2 - start + g[i].first].second + g[i].second);
        
        if(i > 0)
        {
            --i;
            if(D - i - 2 - f[i].first - start >= 0)
                ans = max(ans, g[D - i - 2 - f[i].first - start].second + f[i].second + a[start]);
            if(D - i - 2 - start + g[i].first >= 0)
                ans = max(ans, f[D - i - 2 - start + g[i].first].second + g[i].second + a[start]);
            ++i;
        }
    }
    return ans;
}

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