Submission #519790

#	Time	Username	Problem	Language	Result	Execution time	Memory
519790		Dasha_Gnedko	Birthday gift (IZhO18_treearray)	C++17	100 / 100	968 ms	83236 KiB

treearray

#include <bits/stdc++.h>

//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

using namespace std;

//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(time(0));

#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sz(a) int32_t(a.size())
#define endl '\n'
//#define int long long

const int N = 2e5 + 100;
const int M = 18;
const int mod = 998244353;
const int inf = 1e9 + 7;

vector < int > g[N];
set < int > st1[N], st2[N];
int up[N][M], tin[N], tout[N], timer, a[N];

void DFS(int v, int pr)
{
    up[v][0] = pr;
    for(int j = 1; j < M; j++)
        up[v][j] = up[up[v][j - 1]][j - 1];
    tin[v] = timer++;
    for(auto to: g[v])
    {
        if (to == pr) continue;
        DFS(to, v);
    }
    tout[v] = timer++;
}

bool upper(int a, int b)
{
    return ((tin[a] <= tin[b]) && (tout[a] >= tout[b]));
}

int LCA(int a, int b)
{
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for(int j = M - 1; j >= 0; j--)
        if (!upper(up[a][j], b)) a = up[a][j];
    return up[a][0];
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // LOCAL

    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].pb(y);
        g[y].pb(x);
    }
    DFS(0, 0);
    for(int i = 0; i < m; i++)
    {
        cin >> a[i];
        a[i]--;
        st2[a[i]].insert(i);
        if (i) st1[LCA(a[i - 1], a[i])].insert(i - 1);
    }
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int i, x;
            cin >> i >> x;
            i--; x--;
            st2[a[i]].erase(i);
            if (i) st1[LCA(a[i - 1], a[i])].erase(i - 1);
            if (i + 1 < m) st1[LCA(a[i], a[i + 1])].erase(i);
            a[i] = x;
            st2[a[i]].insert(i);
            if (i) st1[LCA(a[i - 1], a[i])].insert(i - 1);
            if (i + 1 < m) st1[LCA(a[i], a[i + 1])].insert(i);
        }
        if (type == 2)
        {
            int l, r, x;
            cin >> l >> r >> x;
            l--; r--; x--;
            auto it = st2[x].lower_bound(l);
            if (it != st2[x].end())
            {
                int p = *(it);
                if (p <= r)
                {
                    cout << p + 1 << " " << p + 1 << endl;
                    continue;
                }
            }
            it = st1[x].lower_bound(l);
            if (it != st1[x].end())
            {
                int p = *(it);
                if (p < r)
                {
                    cout << p + 1 << " " << p + 2 << endl;
                    continue;
                }
            }
            cout << "-1 -1" << endl;
        }
    }

}

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