Submission #1020630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020630		Ice_man	Holiday (IOI14_holiday)	C++14	100 / 100	402 ms	8968 KiB

holiday

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>

#include "holiday.h"

#define maxn 100005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

using namespace std;


typedef long long ll;
typedef pair <ll , ll> pii;



pii tree[maxn * 4];
ll ta[maxn * 4];
ll a[maxn * 4];
ll n;

void update(ll node , ll l , ll r , ll qp , ll qval)
{
    if(l > qp)
        return;
    if(r < qp)
        return;


    if(l == r)
    {
        tree[node].X += qval;
        tree[node].Y += qval * ta[l];

        return;
    }

    ll mid = (l + r) / 2;

    update(node * 2 , l , mid , qp , qval);
    update(node * 2 + 1 , mid + 1 , r , qp , qval);

    tree[node].X = tree[node * 2].X + tree[node * 2 + 1].X;
    tree[node].Y = tree[node * 2].Y + tree[node * 2 + 1].Y;
}


ll query(ll node , ll l , ll r , ll br)
{
    if(l == r)
        return ta[l] * br;

    ll mid = (l + r) / 2;

    if(br - tree[node * 2 + 1].X > 0)
        return query(node * 2 , l , mid , br - tree[node * 2 + 1].X)
                + tree[node * 2 + 1].Y;
    else
        return query(node * 2 + 1 , mid + 1 , r , br);
}





ll le , ri;
ll sz;

ll dist , start;
ll dp[maxn];

void dnc(ll l , ll r , ll optl , ll optr)
{
    //cout << l << " " << r << endl;

    if(l > r)
        return;
    ll mid = (l + r) / 2;

    while(le < mid)
    {
        update(1 , 1 , sz , a[le] , -1);
        le++;
    }

    while(le > mid)
    {
        le--;
        update(1 , 1 , sz , a[le] , 1);
    }

    while(ri < optl)
    {
        ri++;
        update(1 , 1 , sz , a[ri] , 1);
    }

    while(ri > optl)
    {
        update(1 , 1 , sz , a[ri] , -1);
        ri--;
    }

    ll new_opt = -1;
    for(ll i = optl; i <= optr; i++)
    {
        if(i != optl)
        {
            ri++;
            update(1 , 1 , sz , a[ri] , 1);
        }

        ll br = max(dist - start + mid * 2 - i ,
                    dist - i * 2 + start + mid);
        br = min(br , i - mid + 1);

        ll q = query(1 , 1 , sz , br);
        if(q > dp[mid])
        {
            dp[mid] = q;
            new_opt = i;
        }
    }

    dnc(l , mid - 1 , optl , new_opt);
    dnc(mid + 1 , r , new_opt , optr);
}









ll findMaxAttraction(int N , int START , int D , int attraction[])

{
    n = N;
    start = START;
    dist = D;
    for(ll i = 0; i < n; i++)
        a[i] = attraction[i];

    le = start;
    ri = start - 1;

    vector <ll> val;
    for(ll i = 0; i < n; i++)
        val.pb(a[i]);
    sort(val.begin() , val.end());
    val.erase(unique(val.begin() , val.end()) , val.end());

    sz = val.size();
    //cout << "-> " << sz << endl;

    int save;
    for(int i = 0; i < n; i++)
    {
        save = a[i];
        a[i] = upper_bound(val.begin() , val.end() , a[i]) - val.begin();
        ta[a[i]] = save;

        dp[i] = -LINF;
    }

    /**for(int i = 0; i < val.size(); i++)
        cout << val[i] << endl;
    cout << endl;

    for(int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;

    for(int i = 0; i < n; i++)
        cout << ta[i] << endl;
    cout << endl;
    cout << "----------------------" << endl;*/

    dnc(0 , start , start , n - 1);

    ll ans = 0;
    for(int i = 0; i < n; i++)
        ans = max(ans , dp[i]);

    /**for(int i = 0; i < n; i++)
        cout << dp[i] << " ";
    cout << endl;*/

    return ans;
}





/**int test[maxn];

int main()
{

#ifdef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ///startT = std::chrono::high_resolution_clock::now();

    int nn , startt , dd;

    cin >> nn >> startt >> dd;
    for(int i = 0; i < nn; i++)
        cin >> test[i];

    cout << findMaxAttraction(nn , startt , dd , test) << endl;


    return 0;
}*/

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