Submission #363432

#	Time	Username	Problem	Language	Result	Execution time	Memory
363432		Killer2501	Holiday (IOI14_holiday)	C++14	100 / 100	2009 ms	14944 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, ll u, ll v)
{
    if(l == r)
    {
        cnt[id] = u;
        sum[id] = v;
        return;
    }
    ll mid = (l + r) / 2;
    if(mid >= pos)update(id*2, l, mid, pos, u, v);
    else update(id*2+1, mid+1, r, pos, u, v);
    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(cnt[id] <= k)return sum[id];
  if(k < 0)return -mod;
    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]);
}
bool cmp(ll& x, ll& y)
{
    return a[x] > a[y];
}
void add(ll cl, ll cr)
{
    while(u < cl)
    {
        update(1, 1, n, b[u], 0, 0);
        ++u;
    }
    while(u > cl)
    {
        --u;
        update(1, 1, n, b[u], 1, p[b[u]].fi);
    }
    while(v < cr)
    {
        ++v;
        update(1, 1, n, b[v], 1, p[b[v]].fi);
    }
    while(v > cr)
    {
        update(1, 1, n, b[v], 0, 0);
        --v;
    }
}
void call(ll l, ll r, ll opl, ll opr)
{
    if(l > r)return;
    ll mid = (l + r) / 2;
    ll best = mid, val = -1;
    //cout << l <<" "<<r<<" "<<mid<<" "<<opl<< " "<<opr<<endl;
    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 << 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 = -1, val = -1;
    for(int i = opl; i <= min(mid, opr); i ++)
    {
        k = m - (mid-i+s-i);
        add(i, mid);
        if(get(1, 1, n, k) > val)
        {
            val = get(1, 1, n, k);
            best = i;
        }
    }
    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 = 2, v = 1;
    call(s, n, 1, n);
    fill_n(sum, n*4+2, 0);
    fill_n(cnt, n*4+2, 0);
    u = 2, v = 1;
  	s = n - s + 1;
    for(int i = 1; i <= n; i ++)
    {
        p[n-i+1].fi = -attraction[i-1];
        p[n-i+1].se = n-i+1;
    }
    sort(p+1, p+1+n);
    for(int i = 1; i <= n; i ++)
    {
        p[i].fi *= -1;
        b[p[i].se] = i;
    }
    call(s, n, 1, n);
    return ans;
}

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