Submission #91999

#	Time	Username	Problem	Language	Result	Execution time	Memory
91999		popovicirobert	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1271 ms	101072 KiB

treearray

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 2e5;
const int LOG = 19;

vector <int> g[MAXN + 1];
int lvl[MAXN + 1];

int rmq[2 * MAXN + 1][LOG + 1];
int first[MAXN + 1], sz;

void dfs(int nod, int par) {
    rmq[++sz][0] = nod;
    first[nod] = sz;
    lvl[nod] = lvl[par] + 1;
    for(auto it : g[nod]) {
        if(it != par) {
            dfs(it, nod);
            rmq[++sz][0] = nod;
        }
    }
}

char lg[2 * MAXN + 1];

inline void prec(int n) {
    dfs(1, 0);
    for(int i = 2; i <= sz; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    for(int bit = 1; (1 << bit) <= sz; bit++) {
        for(int i = 1; i + (1 << bit) <= sz + 1; i++) {
            int a = rmq[i][bit - 1], b = rmq[i + (1 << (bit - 1))][bit - 1];
            if(lvl[a] < lvl[b])
                rmq[i][bit] = a;
            else
                rmq[i][bit] = b;
        }
    }
}

inline int get(int x, int y) {
    x = first[x], y = first[y];
    if(x > y) {
        swap(x, y);
    }
    int bit = lg[y - x + 1];
    int a = rmq[x][bit], b = rmq[y - (1 << bit) + 1][bit];
    if(lvl[a] < lvl[b])
        return a;
    return b;
}

int arr[MAXN + 1];

multiset <int> mst1[MAXN + 1], mst2[MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m, q;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> q;
    for(i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    prec(n);
    for(i = 1; i<= m; i++) {
        cin >> arr[i];
    }
    for(i = 1; i <= m; i++) {
        mst1[arr[i]].insert(i);
        if(i < m) {
            mst2[get(arr[i], arr[i + 1])].insert(i);
        }
    }
    while(q > 0) {
        q--;
        int type;
        cin >> type;
        if(type == 1) {
            int pos, nod;
            cin >> pos >> nod;
            mst1[arr[pos]].erase(mst1[arr[pos]].find(pos));
            mst1[nod].insert(pos);
            if(pos > 1) {
                int x = get(arr[pos], arr[pos - 1]);
                mst2[x].erase(mst2[x].find(pos - 1));
                x = get(nod, arr[pos - 1]);
                mst2[x].insert(pos - 1);
            }
            if(pos < m) {
                int x = get(arr[pos], arr[pos + 1]);
                mst2[x].erase(mst2[x].find(pos));
                x = get(nod, arr[pos + 1]);
                mst2[x].insert(pos);
            }
            arr[pos] = nod;
        }
        else {
            int l, r, nod;
            cin >> l >> r >> nod;
            pair <int, int> ans = {-1, -1};
            if(mst1[nod].lower_bound(l) != mst1[nod].end()) {
                auto it = mst1[nod].lower_bound(l);
                if(*it <= r) {
                    ans = {*it, *it};
                }
            }
            if(mst2[nod].lower_bound(l) != mst2[nod].end()) {
                auto it = mst2[nod].lower_bound(l);
                if(*it < r) {
                    ans = {*it, *it + 1};
                }
            }
            cout << ans.first << " " << ans.second << "\n";
        }
    }
    //cin.close();
    //cout.close();
    return 0;
}

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