Submission #755562

#	Time	Username	Problem	Language	Result	Execution time	Memory
755562		teokakabadze	Birthday gift (IZhO18_treearray)	C++17	0 / 100	61 ms	95820 KiB

treearray

#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
#define N 400005
#define M 1000000007
#define pii pair<int, int>
#define piii pair<pii, int>
using namespace std;

int n, m, q, t, c[N], h[N], k[N][30], l[N], pos, val, L, R;
vector<int> v[N];
multiset<int> s[N], s1[N];
multiset<int> :: iterator it;

void dfs(int u, int p)
{
    h[u] = h[p] + 1;
    k[u][0] = p;
    for(auto x : v[u])
    if(x != p) dfs(x, u);
}

int lca(int a, int b)
{
    int i;
    if(h[a] < h[b]) swap(a, b);
    for(i = 20; i >= 0; i--)
    if(h[k[a][i]] >= h[b]) a = k[a][i];
    if(a == b) return a;
    for(i = 20; i >= 0; i--)
    if(k[a][i] != k[b][i]) a = k[a][i], b = k[b][i];
    return k[a][0];
}

main()
{
    std::ios::sync_with_stdio(0);
    cin.tie();
    
    int a, b, i, j;
    cin >> n >> m >> q;
    for(i = 1; i < n; i++)
    {
        cin >> a >> b;
        v[a].pb(b);
        v[b].pb(a);
    }
    dfs(1, 0);
    for(j = 1; j <= 20; j++)
    for(i = 1; i <= n; i++)
    k[i][j] = k[k[i][j - 1]][j - 1];
    for(i = 1; i <= m; i++)
    {
        cin >> c[i];
        s[c[i]].insert(i);
        if(i > 1) l[i] = lca(c[i], c[i - 1]);
        s1[l[i]].insert(i);
    }
    while(q--)
    {
        cin >> t;
        if(t == 1)
        {
            cin >> pos >> val;
            it = s[c[pos]].lower_bound(pos);
            s[c[pos]].erase(it);
            c[pos] = val;
            s[val].insert(pos);
            
            it = s1[l[pos]].lower_bound(pos);
            s1[l[pos]].erase(it);
            l[pos] = lca(c[pos], c[pos - 1]);
            s1[l[pos]].insert(pos);
            
            it = s1[l[pos + 1]].lower_bound(pos + 1);
            s1[l[pos + 1]].erase(it);
            l[pos + 1] = lca(c[pos + 1], c[pos]);
            s1[l[pos + 1]].insert(pos + 1);
        }
        else
        {
            cin >> L >> R >> val;
            it = s[val].lower_bound(L);
            if(it != s[val].end() && *it <= R) { cout << *it << ' ' << *it << '\n'; continue; }
            it = s1[val].lower_bound(L + 1);
            if(it != s1[val].end() && *it <= R) cout << *it - 1 << ' ' << *it << '\n';
            else cout << "-1 -1\n";
        }
    }
}

Compilation message (stderr)

treearray.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main()
      | ^~~~

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