Submission #750576

#	Time	Username	Problem	Language	Result	Execution time	Memory
750576		anaduguleanu	Birthday gift (IZhO18_treearray)	C++14	56 / 100	2441 ms	92164 KiB

treearray

#include <iostream>
#include <vector>
#include <set>
#define LOG 20
#define MAX 200000
using namespace std;
///ifstream cin ("c.in");
///ofstream cout ("c.out");
long long a[MAX + 10], level[MAX + 10], ancestor[LOG + 10][MAX + 10];
vector <long long> graph[MAX + 10];
set <long long> posSequence[MAX + 10], posLca[MAX + 10];
void dfs(long long node, long long parent, long long depth)
{
    level[node] = depth;
    for (auto next : graph[node])
        if (next != parent)
        {
            ancestor[0][next] = node;
            dfs(next, node, depth + 1);
        }
}
long long lca(long long x, long long y)
{
    if (level[y] > level[x])
        swap(x, y);
    for (long long p = LOG; p >= 0; p--)
        if (level[ancestor[p][x]] >= level[y])
            x = ancestor[p][x];
    if (x == y)
        return x;
    for (long long p = LOG; p >= 0; p--)
        if (ancestor[p][x] != ancestor[p][y])
        {
            x = ancestor[p][x];
            y = ancestor[p][y];
        }
    return ancestor[0][x];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, m, q;
    cin >> n >> m >> q;
    for (long long i = 1; i < n; i++)
    {
        long long x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    for (long long p = 0; p <= LOG; p++)
        ancestor[p][1] = 1;
    dfs(1, 0, 0);
    for (long long p = 1; p <= LOG; p++)
        for (long long node = 2; node <= n; node++)
            ancestor[p][node] = ancestor[p - 1][ancestor[p - 1][node]];
    for (long long i = 1; i <= m; i++)
    {
        cin >> a[i];
        posSequence[a[i]].insert(i);
    }
    for (long long i = 1; i < m; i++)
        posLca[lca(a[i], a[i + 1])].insert(i);
    for (long long qq = 1; qq <= q; qq++)
    {
        long long type;
        cin >> type;
        if (type == 1)
        {
            long long pos, val;
            cin >> pos >> val;
            posSequence[a[pos]].erase(pos);
            posSequence[val].insert(pos);
            if (pos < n)
            {
                posLca[lca(a[pos], a[pos + 1])].erase(pos);
                posLca[lca(val, a[pos + 1])].insert(pos);
            }
            if (pos > 1)
            {
                posLca[lca(a[pos - 1], a[pos])].erase(pos - 1);
                posLca[lca(a[pos - 1], val)].insert(pos - 1);
            }
            a[pos] = val;
        }
        else
        {
            long long l, r, valLca;
            cin >> l >> r >> valLca;
            auto it = posSequence[valLca].lower_bound(l);
            if (it != posSequence[valLca].end() && *it <= r)
                cout << *it << ' ' << *it << '\n';
            else
            {
                it = posLca[valLca].lower_bound(l);
                if (it != posLca[valLca].end() && *it < r)
                    cout << *it << ' ' << (*it) + 1 << '\n';
                else
                    cout << "-1 1\n";
            }
        }
    }
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 0 / 44