Submission #363197

#	Time	Username	Problem	Language	Result	Execution time	Memory
363197		Killer2501	Holiday (IOI14_holiday)	C++14	0 / 100	1745 ms	14476 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
#define pb push_back
#define task "sequence"
#define pll pair<ll, ll>
#define pii pair<vector<ll>, ll>
#define fi first
#define se second
using ll = long long;
const long long mod = 1e15+7;
const ll mod1 = 1e9+1;
const ll N = 2e5+5;
const int base = 350;
using ull = unsigned long long;
using namespace std;
ll n, m, t, k, T, u, tong, v, a[N], ans, c[N], d[N], b[N], sum[N*4], cnt[N*4], s;
vector<ll> adj[N], kq;
vector<pll> l, r;
pll p[N];
void update(ll id, ll l, ll r, ll pos)
{
    if(l == r)
    {
        if(cnt[id] == 0)
        {
            cnt[id] = 1;
            sum[id] = p[l].fi;
        }
        else
        {
            cnt[id] = 0;
            sum[id] = 0;
        }
        return;
    }
    ll mid = (l + r) / 2;
    if(mid >= pos)update(id*2, l, mid, pos);
    else update(id*2+1, mid+1, r, pos);
    sum[id] = sum[id*2] + sum[id*2+1];
    cnt[id] = cnt[id*2] + cnt[id*2+1];
}
ll get(ll id, ll l, ll r, ll k)
{
    //if(t == 1)cout << l <<" "<<r<<" "<<k<<" "<<sum[id]<<" " << cnt[id] <<" "<<cnt[id*2]<< '\n';
    if(cnt[id] <= k)return sum[id];
    if(k <= 0 || l == r)return 0;
    ll mid = (l + r) / 2;
    if(cnt[id*2] >= k)return get(id*2, l, mid, k);
    else return sum[id*2] + get(id*2+1, mid+1, r, k-cnt[id*2]);
}

void add(ll cl, ll cr)
{
    while(u < cl)
    {
        update(1, 1, n, b[u]);
        ++u;
    }
    while(u > cl)
    {
        --u;
        update(1, 1, n, b[u]);
    }
    while(v < cr)
    {
        ++v;
        update(1, 1, n, b[v]);
    }
    while(v > cr)
    {
        update(1, 1, n, b[v]);
        --v;
    }
}
void call(ll l, ll r, ll opl, ll opr)
{
    if(l > r)return;
    ll mid = (l + r) / 2;
    ll best = opl, val = -1;

    for(int i = opl; i <= min(mid, opr); i ++)
    {
        k = m - (mid-i+mid-s);
        //cout << "ok"<<" ";
        add(i, mid);

        if(get(1, 1, n, k) > val)
        {
            val = get(1, 1, n, k);
            best = i;
        }
        //cout << "ok" <<" ";
    }
    //cout << l <<" "<<r<<" "<<mid<<" "<<opl<< " "<<opr<<" "<<val<<endl;
    //cout << l <<" "<< r << " " << mid << endl;;
    ans = max(ans, val);
    call(l, mid-1, opl, best);
    call(mid+1, r, best, opr);
}
void calr(ll l, ll r, ll opl, ll opr)
{
    if(l > r)return;
    ll mid = (l + r) / 2;
    ll best = opl, val = -1;
    for(int i = opl; i <= min(mid, opr); i ++)
    {
        k = m - (mid-i+s-i);
        //if(k <= 0)continue;
        add(i, mid);
        if(get(1, 1, n, k) > val)
        {
            val = get(1, 1, n, k);
            best = i;
        }
    }
    //cout << mid <<" "<<val<<" "<<best<<'\n';
    ans = max(ans, val);
    calr(l, mid-1, opl, best);
    calr(mid+1, r, best, opr);
}
ll findMaxAttraction(int _n, int start, int _d, int attraction[])
{
    n = _n;
    s = start+1;
    m = _d;
    for(int i = 1; i <= n; i ++)
    {
        p[i].fi = -attraction[i-1];
        p[i].se = i;
    }
    sort(p+1, p+1+n);
    for(int i = 1; i <= n; i ++)
    {
        p[i].fi *= -1;
        b[p[i].se] = i;
    }
    u = 1, v = 0;
    call(s, n, 1, n);
    fill_n(sum, n*4+2, 0);
    fill_n(cnt, n*4+2, 0);
    u = 1, v = 0;
    calr(s, n, 1, n);
    return ans;
}

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