Submission #775458

#	Time	Username	Problem	Language	Result	Execution time	Memory
775458		boris_mihov	Holiday (IOI14_holiday)	C++17	100 / 100	1799 ms	16196 KiB

holiday

#include "holiday.h"
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
#include <queue>
#include <set>

typedef long long llong;
const int MAXN = 100000 + 10;
const int INF  = 1e9;

int n;
int a[MAXN];
std::unordered_map <int,int> mp;
std::mt19937 mt(69420);

struct Treap
{
    struct Node
    {
        int x, y;
        int sz;
        llong sumX;
        Node *left, *right;
    
        Node()
        {
            left = right = nullptr;
        }

        Node(int _x, int _y)
        {
            x = _x;
            y = _y;
            sz = 1;
            sumX = x;
            left = right = nullptr;
        }
    };

    Node *root;
    Node *pNode[MAXN];

    void recover(Node *curr)
    {
        if (curr == nullptr)
        {
            return;
        }

        curr->sz = 1;
        curr->sumX = curr->x;

        if (curr->left != nullptr)
        {
            curr->sz += curr->left->sz;
            curr->sumX += curr->left->sumX;            
        }

        if (curr->right != nullptr)
        {
            curr->sz += curr->right->sz;
            curr->sumX += curr->right->sumX;            
        }
    }

    void splitSIZE(Node *curr, Node *&left, Node *&right, int k)
    {
        if (curr == nullptr)
        {
            left = right = nullptr;
            return;
        }

        int sz = 1;
        if (curr->left != nullptr)
        {
            sz += curr->left->sz;
        }

        if (k >= sz)
        {
            left = curr;
            splitSIZE(curr->right, left->right, right, k - sz);
            recover(left);
        } else
        {
            right = curr;
            splitSIZE(curr->left, left, right->left, k);
            recover(right);
        }
    }

    void splitVALUE(Node *curr, Node *&left, Node *&right, int k)
    {
        if (curr == nullptr)
        {
            left = right = nullptr;
            return;
        }

        if (curr->x < k)
        {
            left = curr;
            splitVALUE(curr->right, left->right, right, k);
            recover(left);
        } else
        {
            right = curr;
            splitVALUE(curr->left, left, right->left, k);
            recover(right);
        }
    }

    void merge(Node *&curr, Node *left, Node *right)
    {
        if (left == nullptr)
        {
            curr = right;
            return;
        }

        if (right == nullptr)
        {
            curr = left;
            return;
        }

        if (left->y > right->y)
        {
            curr = left;
            merge(curr->right, left->right, right);
        } else
        {
            curr = right;
            merge(curr->left, left, right->left);
        }

        recover(curr);
    }

    void build()
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            pNode[i] = new Node(a[i], mt());
        }
    }

    void insert(int idx)
    {
        Node *l, *r;
        splitVALUE(root, l, r, a[idx]);
        merge(l, l, pNode[idx]);
        merge(root, l, r);
    }

    void erase(int idx)
    {
        Node *l, *r, *nz;
        splitVALUE(root, l, r, a[idx]);
        splitSIZE(r, nz, r, 1);
        std::swap(pNode[idx], nz);
        merge(root, l, r);
    }

    llong findLargest(int k)
    {
        k = std::min(k, root->sz);
        Node *left, *right;
        splitSIZE(root, left, right, root->sz - k);
        llong res = right->sumX;
        merge(root, left, right);
        return res;
    }

    std::vector <int> vals;
    void printTreap(Node *curr)
    {
        if (curr == nullptr)
        {
            return;
        }
        
        vals.push_back(curr->x);
        printTreap(curr->left);
        printTreap(curr->right);
    }

    void printTreap()
    {
        vals.clear();
        printTreap(root);
        std::cout << "treap has\n";
        for (const int &i : vals)
        {
            std::cout << i << ' ';
        }

        std::cout << '\n';
    }
};

int pos, d;
llong ans;
Treap treap;


int moL = 1;
int moR = 0;

llong getCost(int l, int r)
{
    while (moL > l) treap.insert(--moL);
    while (moR < r) treap.insert(++moR);
    while (moL < l) treap.erase(moL++);
    while (moR > r) treap.erase(moR--);
    return treap.findLargest(d - pos + 2 * l - r);
}

void rec(int l, int r, int optL, int optR)
{
    if (d - pos + 2 * r - optL <= 0)
    {
        return;
    }

    int opt = -1;
    int mid = (l + r) / 2;
    llong currSum = 0;
    llong currRes = 0;

    for (int i = optL ; i <= optR && d - pos + 2 * mid - i > 0 ; ++i)
    {
        currSum = getCost(mid, i);
        if (currSum > currRes)
        {
            opt = i;
            currRes = currSum;
        }
    }

    if (opt == -1)
    {
        opt = optL;
    }

    if (l < mid) rec(l, mid - 1, optL, opt);
    if (mid < r) rec(mid + 1, r, opt, optR);
    ans = std::max(ans, currRes);
}

llong findMaxAttraction(int N, int start, int D, int A[])
{
    n = N;
    d = D;
    pos = start + 1;
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = A[i - 1];
    }

    int cnt = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (!mp.count(a[i]))
        {
            mp[a[i]] = ++cnt;
        }
    }

    treap.build();
    if (pos <= n)
    {
        rec(1, pos, pos + 1, n);
    }

    std::reverse(a + 1, a + 1 + n);
    pos = n - pos + 1;
    treap.root = nullptr;
    treap.build();
    moL = 1;
    moR = 0;

    if (pos <= n) 
    {
        rec(1, pos, pos + 1, n);
    }

    return ans;
}

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