Submission #1020549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020549		Ice_man	Holiday (IOI14_holiday)	C++14	0 / 100	850 ms	3544 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 pair <int, int> pii;
typedef long long ll;
typedef pair <ll , ll> pll;
typedef pair <int , ll> pil;
typedef pair <ll , int> pli;
typedef long double ld;


std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}



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

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


    if(l == r)
    {
        tree[node] = {qval , qval * ta[l]};
        return;
    }

    int mid = (l + r) / 2;

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

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


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

    int 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);
}





int le , ri;
int sz;

int dist , start;
int dp[maxn];

void dnc(int l , int r , int optl , int optr)
{
    if(l > r)
        return;
    int 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--;
    }

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

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

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

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









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

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

    le = start;
    ri = start - 1;

    vector <int> val;
    for(int 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();

    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] = -INF;
    }

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

    return *max_element(dp , dp + n);
}





/**
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();

    read();
    solve();


    return 0;
}
*/

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