Submission #113564

#	Time	Username	Problem	Language	Result	Execution time	Memory
113564		FutymyClone	Birthday gift (IZhO18_treearray)	C++14	12 / 100	44 ms	27072 KiB

treearray

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, m, q, a[N], h[N], par[20][N], st[N], en[N], cnt = 0;
vector <int> g[N];

void dfs (int u, int p) {
    st[u] = ++cnt;
    for (auto v: g[u]) {
        if (v == p) continue;
        h[v] = h[u] + 1;
        par[0][v] = u;
        dfs(v, u);
    }

    en[u] = cnt;
}

void makeLCA(){
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j <= n; j++) {
            if (par[i - 1][j] != -1) par[i][j] = par[i - 1][par[i - 1][j]];
        }
    }
}

int LCA (int x, int y) {
    if (x == 0) return y;
    if (y == 0) return x;
    if (h[x] > h[y]) swap(x, y);
    for (int i = 19; i >= 0; i--) if (par[i][y] != -1 && h[y] - (1 << i) >= h[x]) y = par[i][y];
    if (x == y) return x;
    for (int i = 19; i >= 0; i--) {
        if (par[i][x] != -1 && par[i][y] != -1 && par[i][x] != par[i][y]) {
            x = par[i][x];
            y = par[i][y];
        }
    }

    if (x == y) return x;
    return par[0][x];
}

struct LCAIT {
    int node[N << 2];
    void init (int i, int l, int r) {
        if (l == r) {
            node[i] = a[l];
            return;
        }

        int mid = l + r >> 1;
        init(i << 1, l, mid);
        init(i << 1 | 1, mid + 1, r);
        node[i] = LCA(node[i << 1], node[i << 1 | 1]);
    }

    void update (int i, int l, int r, int pos, int val) {
        if (l == r) {
            node[i] = val;
            return;
        }

        int mid = l + r >> 1;
        if (pos <= mid) update(i << 1, l, mid, pos, val);
        else update(i << 1 | 1, mid + 1, r, pos, val);
        node[i] = LCA(node[i << 1], node[i << 1 | 1]);
    }

    int query (int i, int l, int r, int a, int b) {
        if (l > r || a > r || b < l) return 0;
        if (a <= l && r <= b) return node[i];

        int mid = l + r >> 1;
        return LCA(query(i << 1, l, mid, a, b), query(i << 1 | 1, mid + 1, r, a, b));
    }
} lcait;

struct ProneIT {
    struct Node {
        int Min, Max;
        Node (int Min = 0, int Max = 0): Min(Min), Max(Max) {}
        Node operator + (const Node &rhs) const {
            return Node(min(Min, rhs.Min), max(Max, rhs.Max));
        }
    } node[N << 2];

    void init (int i, int l, int r) {
        if (l == r) {
            node[i] = Node(st[a[l]], st[a[l]]);
            return;
        }

        int mid = l + r >> 1;
        init(i << 1, l, mid);
        init(i << 1 | 1, mid + 1, r);
        node[i] = node[i << 1] + node[i << 1 | 1];
    }

    void update (int i, int l, int r, int pos, int val) {
        if (l == r) {
            node[i] = Node(st[val], st[val]);
            return;
        }

        int mid = l + r >> 1;
        if (pos <= mid) update(i << 1, l, mid, pos, val);
        else update(i << 1 | 1, mid + 1, r, pos, val);
        node[i] = node[i << 1] + node[i << 1 | 1];
    }

    Node query (int i, int l, int r, int a, int b) {
        if (l > r || a > r || b < l) return Node(1e9, -1e9);
        if (a <= l && r <= b) return node[i];

        int mid = l + r >> 1;
        return query(i << 1, l, mid, a, b) + query(i << 1 | 1, mid + 1, r, a, b);
    }

    int prone_max_left (int i, int l, int r, int a, int b, int val) {
        if (l > r || a > r || b < l) return -1;
        if (a <= l && r <= b) {
            if (node[i].Max <= val) return l;
        }

        if (l == r) {
            if (node[i].Max <= val) return l;
            return -1;
        }

        int mid = l + r >> 1;
        int cur = prone_max_left(i << 1, l, mid, a, b, val);
        if (cur != -1) return cur;
        return prone_max_left(i << 1 | 1, mid + 1, r, a, b, val);
    }

    int prone_min_left (int i, int l, int r, int a, int b, int val) {
        if (l > r || a > r || b < l) return -1;
        if (a <= l && r <= b) {
            if (node[i].Min >= val) return l;
        }

        if (l == r) {
            if (node[i].Min >= val) return l;
            return -1;
        }

        int mid = l + r >> 1;
        int cur = prone_min_left(i << 1, l, mid, a, b, val);
        if (cur != -1) return cur;
        return prone_min_left(i << 1 | 1, mid + 1, r, a, b, val);
    }

    int prone_max_right (int i, int l, int r, int a, int b, int val) {
        if (l > r || a > r || b < l) return -1;
        if (a <= l && r <= b) {
            if (node[i].Max <= val) return r;
        }

        if (l == r) {
            if (node[i].Max <= val) return l;
            return -1;
        }

        int mid = l + r >> 1;
        int cur = prone_max_right(i << 1 | 1, mid + 1, r, a, b, val);
        if (cur != -1) return cur;
        return prone_max_right(i << 1, l, mid, a, b, val);
    }

    int prone_min_right (int i, int l, int r, int a, int b, int val) {
        if (l > r || a > r || b < l) return -1;
        if (a <= l && r <= b) {
            if (node[i].Min >= val) return r;
        }

        if (l == r) {
            if (node[i].Min >= val) return l;
            return -1;
        }

        int mid = l + r >> 1;
        int cur = prone_min_right(i << 1 | 1, mid + 1, r, a, b, val);
        if (cur != -1) return cur;
        return prone_min_right(i << 1, l, mid, a, b, val);
    }

    pair <int, pair <int, int> > solve (int i, int l, int r, int a, int b, int v) {
        if (l > r || a > r || b < l) return {-1, {-1, -1}};
        if (a <= l && r <= b) {
            if (lcait.node[i] == v) return {lcait.node[i], {l, r}};
        }

        if (l == r) return {lcait.node[i], {l, r}};

        int mid = l + r >> 1;
        pair <int, pair <int, int> > lef = solve(i << 1, l, mid, a, b, v);
        pair <int, pair <int, int> > rig = solve(i << 1 | 1, mid + 1, r, a, b, v);
        if (lef.first == v) return lef;
        if (rig.first == v) return rig;

        int maxlef = prone_max_left(1, 1, m, l, mid, en[v]);
        int minlef = prone_min_left(1, 1, m, l, mid, st[v]);
        int maxrig = prone_max_right(1, 1, m, mid + 1, r, en[v]);
        int minrig = prone_min_right(1, 1, m, mid + 1, r, st[v]);

        if (maxlef == -1 || minlef == -1 || maxrig == -1 || minrig == -1) return {-1, {-1, -1}};

        int lefpos = max(maxlef, minlef);
        int rigpos = min(maxrig, minrig);
        lefpos = max(lefpos, a);
        rigpos = min(rigpos, b);
        int get_lca = lcait.query(1, 1, m, lefpos, rigpos);
        return {get_lca, {lefpos, rigpos}};
    }
} proneit;

int main(){
    scanf("%d %d %d", &n, &m, &q); memset(par, -1, sizeof(par));
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
    dfs(1, 1);
    makeLCA();
    lcait.init(1, 1, m);
    proneit.init(1, 1, m);

    while (q--) {
        int type;
        scanf("%d", &type);
        if (type == 1) {
            int pos, v;
            scanf("%d %d", &pos, &v);
            lcait.update(1, 1, m, pos, v);
            proneit.update(1, 1, m, pos, v);
        }
        else {
            int l, r, v;
            scanf("%d %d %d", &l, &r, &v);
            pair <int, pair <int, int> > ans = proneit.solve(1, 1, m, l, r, v);
            if (ans.first == v) printf("%d %d\n", ans.second.first, ans.second.second);
            else printf("%d %d\n", -1, -1);
        }
    }
    return 0;
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1

7 5 3
1 2
3 1
3 4
5 3
5 6
5 7
2 6 6 4 1
2 1 5 3
1 3 6
2 1 5 3
*/

Compilation message (stderr)

treearray.cpp: In member function 'void LCAIT::init(int, int, int)':
treearray.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
treearray.cpp: In member function 'void LCAIT::update(int, int, int, int, int)':
treearray.cpp:67:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
treearray.cpp: In member function 'int LCAIT::query(int, int, int, int, int)':
treearray.cpp:77:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
treearray.cpp: In member function 'void ProneIT::init(int, int, int)':
treearray.cpp:97:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
treearray.cpp: In member function 'void ProneIT::update(int, int, int, int, int)':
treearray.cpp:109:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
treearray.cpp: In member function 'ProneIT::Node ProneIT::query(int, int, int, int, int)':
treearray.cpp:119:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
treearray.cpp: In member function 'int ProneIT::prone_max_left(int, int, int, int, int, int)':
treearray.cpp:134:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
treearray.cpp: In member function 'int ProneIT::prone_min_left(int, int, int, int, int, int)':
treearray.cpp:151:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
treearray.cpp: In member function 'int ProneIT::prone_max_right(int, int, int, int, int, int)':
treearray.cpp:168:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
treearray.cpp: In member function 'int ProneIT::prone_min_right(int, int, int, int, int, int)':
treearray.cpp:185:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
treearray.cpp: In member function 'std::pair<int, std::pair<int, int> > ProneIT::solve(int, int, int, int, int, int)':
treearray.cpp:199:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
treearray.cpp: In function 'int main()':
treearray.cpp:222:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q); memset(par, -1, sizeof(par));
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:225:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~
treearray.cpp:230:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
                                  ~~~~~^~~~~~~~~~~~~
treearray.cpp:238:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &type);
         ~~~~~^~~~~~~~~~~~~
treearray.cpp:241:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &pos, &v);
             ~~~~~^~~~~~~~~~~~~~~~~~~
treearray.cpp:247:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d %d", &l, &r, &v);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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