Submission #750573

#	Time	Username	Problem	Language	Result	Execution time	Memory
750573		anaduguleanu	Birthday gift (IZhO18_treearray)	C++14	Compilation error	0 ms	0 KiB

treearray

#include <iostream>
#include <vector>
#include <set>
typedef long long ll;
#define LOG 20
#define MAX 200000
#define int ll
using namespace std;
///ifstream cin ("c.in");
///ofstream cout ("c.out");
int a[MAX + 10], level[MAX + 10], ancestor[LOG + 10][MAX + 10];
vector <int> graph[MAX + 10];
set <int> posSequence[MAX + 10], posLca[MAX + 10];
void dfs(int node, int parent, int depth)
{
    level[node] = depth;
    for (auto next : graph[node])
        if (next != parent)
        {
            ancestor[0][next] = node;
            dfs(next, node, depth + 1);
        }
}
int lca(int x, int y)
{
    if (level[y] > level[x])
        swap(x, y);
    for (int p = LOG; p >= 0; p--)
        if (level[ancestor[p][x]] >= level[y])
            x = ancestor[p][x];
    if (x == y)
        return x;
    for (int 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()
{
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    for (int p = 0; p <= LOG; p++)
        ancestor[p][1] = 1;
    dfs(1, 0, 0);
    for (int p = 1; p <= LOG; p++)
        for (int node = 2; node <= n; node++)
            ancestor[p][node] = ancestor[p - 1][ancestor[p - 1][node]];
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
        posSequence[a[i]].insert(i);
    }
    for (int i = 1; i < m; i++)
        posLca[lca(a[i], a[i + 1])].insert(i);
    for (int qq = 1; qq <= q; qq++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int 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
        {
            int 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;
}

Compilation message (stderr)

treearray.cpp:7:13: error: '::main' must return 'int'
    7 | #define int ll
      |             ^~
treearray.cpp:41:1: note: in expansion of macro 'int'
   41 | int main()
      | ^~~