Submission #808897

#	Time	Username	Problem	Language	Result	Execution time	Memory
808897		htphong0909	Holiday (IOI14_holiday)	C++17	100 / 100	1328 ms	5816 KiB

holiday

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

set<pair<int, int>> selected;
set<pair<int, int>, greater<>> notSelected;
long long curValue = 0;
int lt = 1;
int rt = 0;
int n, d, start;
int cnt;
int arr[100001];
long long ans = -1e18;

void trade()
{
    pair<int, int> temp1 = *notSelected.begin();
    pair<int, int> temp2 = *selected.begin();
    curValue = curValue - temp2.first + temp1.first;
    notSelected.erase(temp1);
    notSelected.insert(temp2);
    selected.erase(temp2);
    selected.insert(temp1);
}

void unselect()
{
    cnt++;
    pair <int, int> temp = *selected.begin();
    notSelected.insert(temp);
    curValue -= temp.first;
    selected.erase(temp);
}

void select()
{
    cnt--;
    pair <int, int> temp = *notSelected.begin();
    selected.insert(temp);
    curValue += temp.first;
    notSelected.erase(temp);
}

void Add(int x)
{
    notSelected.insert(make_pair(arr[x], x));
}

void Del(int x)
{
    if (selected.find(make_pair(arr[x], x)) != selected.end())
    {
        selected.erase(make_pair(arr[x], x));
        curValue -= arr[x];
        cnt++;
        if (!notSelected.empty() && cnt > 0) select();
    }
    else notSelected.erase(make_pair(arr[x], x));
}

int calcDis(int l, int r)
{
    if (l > r) return 0;
    if (start <= l) return(l - start + (r - l));
    if (start >= r) return(start - r + (r - l));
    return (min(start - l, r - start) + (r - l));
}

long long cost(int l, int r)
{
    while (lt != l || rt != r)
    {
        while (rt < r)
        {
            cnt += calcDis(lt, rt) - calcDis(lt, rt + 1);
            rt++;
            Add(rt);
            while (!notSelected.empty() && !selected.empty() && notSelected.begin()->first > (selected.begin())->first) trade();
            while (cnt < 0 && !selected.empty()) unselect();
            while (cnt > 0 && !notSelected.empty()) select();
        }
        while (rt > lt && rt > r)
        {
            cnt += calcDis(lt, rt) - calcDis(lt, rt - 1);
            Del(rt);
            rt--;
            while (!notSelected.empty() && !selected.empty() && notSelected.begin()->first > (selected.begin())->first) trade();
            while (cnt < 0 && !selected.empty()) unselect();
            while (cnt > 0 && !notSelected.empty()) select();
        }
        while (lt < rt && lt < l)
        {
            cnt += calcDis(lt, rt) - calcDis(lt + 1, rt);
            Del(lt);
            lt++;
            while (!notSelected.empty() && !selected.empty() && notSelected.begin()->first > (selected.begin())->first) trade();
            while (cnt < 0 && !selected.empty()) unselect();
            while (cnt > 0 && !notSelected.empty()) select();
        }
        while (lt > l)
        {
            cnt += calcDis(lt, rt) - calcDis(lt - 1, rt);
            lt--;
            Add(lt);
            while (!notSelected.empty() && !selected.empty() && notSelected.begin()->first > (selected.begin())->first) trade();
            while (cnt < 0 && !selected.empty()) unselect();
            while (cnt > 0 && !notSelected.empty()) select();
        }
    }
    return curValue;
}

void divide(int l, int r, int gL, int gR)
{
    if (l > r) return;
    int mid = (l + r) / 2;
    long long bestCost = -1e18;
    int bestPos = gL;
    for (int i = gL; i <= min(mid, gR); i++)
    {
        if (cost(i, mid) > bestCost)
        {
            bestCost = cost(i, mid);
            bestPos = i;
        }
    }
    ans = max(ans, bestCost);
    divide(l, mid - 1, gL, bestPos);
    divide(mid + 1, r, bestPos, gR);
}

long long findMaxAttraction(int _n, int _start, int _d, int *attraction)
{
    n = _n;
    d = _d;
    start = _start + 1;
    for (int i = 1; i <= n; i++) arr[i] = attraction[i - 1];
    cnt = d;
    divide(1, n, 1, n);
    return ans;
}

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