Submission #704169

#	Time	Username	Problem	Language	Result	Execution time	Memory
704169		pls33	Airplanes (LMIO17_lektuvai)	C++17	100 / 100	451 ms	56748 KiB

lektuvai

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
#pragma endregion

void dfs(int v, int &count, vvi32 &adj, vp32 &range)
{
    range[v].first = count;
    count++;

    for (auto &next : adj[v])
    {
        dfs(next, count, adj, range);
    }

    range[v].second = count;
    count++;
}

struct node_t;
deque<node_t> cache;

node_t *get(p32 range)
{
    cache.emplace_back(range);
    return &cache.back();
}

struct node_t
{
    int val;
    p32 range;
    node_t *left, *right;

    node_t(p32 r)
    {
        val = 0;
        range = r;
        left = nullptr;
        right = nullptr;
    }

    void expand()
    {
        if (right || range.second - range.first == 1)
        {
            return;
        }

        int mid = (range.second + range.first) / 2;
        left = get({range.first, mid});
        right = get({mid, range.second});
    }

    void fix()
    {
        if (!right || range.second - range.first == 1)
        {
            return;
        }

        val = max(left->val, right->val);
    }

    int intersect(p32 dest)
    {
        if (dest.first >= range.second || dest.second <= range.first)
        {
            return 0;
        }

        if (dest.first <= range.first && range.second <= dest.second)
        {
            return 1;
        }

        return 2;
    }
};

void update(node_t *node, p32 range, int val)
{
    if (!node || !node->intersect(range))
    {
        return;
    }

    if (node->intersect(range) == 1)
    {
        node->val = val;
        return;
    }

    node->expand();
    update(node->left, range, val);
    update(node->right, range, val);
    node->fix();
}

int query(node_t *node, p32 range)
{
    if (!node || !node->intersect(range))
    {
        return 0;
    }

    if (node->intersect(range) == 1)
    {
        return node->val;
    }

    return max(query(node->left, range), query(node->right, range));
}

int main()
{
#ifndef _AAAAAAAAA
    //freopen("lmio_2017_3e2_lektuvai_vyr.in", "r", stdin);
    //freopen("lmio_2017_3e2_lektuvai_vyr.out", "w", stdout);
#else
    freopen("lektuvai.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int n;
    cin >> n;

    vi32 time(n);
    for (auto &i : time)
    {
        cin >> i;
    }

    vvi32 adj(n);
    for (int i = 0; i < n - 1; i++)
    {
        int j;
        cin >> j;
        j--;

        adj[j].push_back(i);
    }

    vp32 range(n);
    int count = 0;
    dfs(n - 1, count, adj, range);

    node_t *node = get({0, 2 * n});
    for (int i = 0; i < n; i++)
    {
        update(node, {range[i].first, range[i].first + 1}, time[i]);
        update(node, {range[i].second, range[i].second + 1}, time[i]);
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; i++)
    {
        char type;
        cin >> type;

        if (type == 'I')
        {
            int index;
            cin >> index;
            index--;

            cout << query(node, {range[index].first, range[index].second + 1}) << '\n';
        }
        else
        {
            int index, val;
            cin >> index >> val;
            index--;

            p32 r1 = {range[index].first, range[index].first + 1};
            p32 r2 = {range[index].second, range[index].second + 1};

            int subtree = (int)query(node, {range[index].first, range[index].second + 1});

            update(node, r1, subtree + val);
            update(node, r2, subtree + val);
        }
    }

    return 0;
}

Compilation message (stderr)

lektuvai.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
lektuvai.cpp:31: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   31 | #pragma endregion
      |

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 40 / 40
• Subtask 4: 49 / 49