Submission #456462

#	Time	Username	Problem	Language	Result	Execution time	Memory
456462		nafis_shifat	Birthday gift (IZhO18_treearray)	C++14	0 / 100	23 ms	42732 KiB

treearray

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define f first
#define s second
using namespace std;
const int mxn=2e5+5;
const int inf=1e9;
vector<int> adj[mxn];
int n,m,q;
int a[mxn];
int dp[20][mxn];
int level[mxn];
int T = 0;
int in[mxn];
int out[mxn];

int inv[mxn];
void dfs(int cur,int prev) {
    in[cur] = ++T;
    inv[T] = cur;
    dp[0][cur] = prev;
    level[cur] = level[prev] + 1;
    for(int i = 1; i < 20; i++) dp[i][cur] = dp[i - 1][dp[i - 1][cur]];
    for(int u : adj[cur]) {
        if(u != prev) dfs(u,cur);
    }
    out[cur] = T;
}



int getLCA(int u,int v) {
    if(level[u] < level[v]) swap(u,v);

    int dif = level[u] - level[v];
    for(int i = 0; i < 20; i++) if((dif >> i) & 1) u = dp[i][u];
    if(u == v) return v;
    for(int i = 19; i >= 0; i--) {
        if(dp[i][u] != dp[i][v]) {
            u = dp[i][u];
            v = dp[i][v];
        }
    }

    return dp[0][u];
}

struct segtree {
    set<pii> tree[4 * mxn];

    void build(int node,int b,int e) {
        if(b==e) {
            tree[node].insert({in[a[b]],b});
            return;
        }
        int mid=b+e>>1;
        int left=node<<1;
        int right=left|1;

        build(left,b,mid);
        build(right,mid+1,e);
        for(auto i : tree[left]) tree[node].insert(i);
        for(auto i : tree[right]) tree[node].insert(i);
       
    }


    pii query(int node,int b,int e,int l,int r,int v,bool f) {
        if(e < l || b > r) return (f ? mp(-1,-1) : mp(inf,inf));
        if(b >= l && e <= r) {
            if(!f) {
                auto x = tree[node].lower_bound(mp(v,0));
                if(x == tree[node].end()) return mp(inf,inf);
                return *x;
            }             
            auto x = tree[node].lower_bound(mp(v,0));
            if(x == tree[node].end() || *x > mp(v,inf)) {
                if(x == tree[node].begin()) return mp(-1,-1);
                x--;
            }
            return *x;

        }

        int mid=b+e>>1;
        int left=node<<1;
        int right=left|1;

        if(!f) return min(query(left,b,mid,l,r,v,f),query(right,mid + 1,e,l,r,v,f));
        return max(query(left,b,mid,l,r,v,f),query(right,mid + 1,e,l,r,v,f));    
    }


    void update(int node,int b,int e,int p,int v) {
        if(e < p || b > p) return;

        tree[node].erase({in[a[p]],p});
        tree[node].insert({in[v],p});
        if(b == e) return;

        int mid = b + e >> 1;
        int left = node << 1;
        int right = left | 1;

        update(left,b,mid,p,v);
        update(right,mid + 1,e,p,v);
    }
} st;


int main() {

    cin >> n >> m >> q;

    for(int i = 1; i < n; i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1; i <= m; i++) {
        scanf("%d",&a[i]);
    }

    
    

    dfs(1,0);

    st.build(1,1,m);
    

    while(q--) {
        int tp;
        scanf("%d",&tp);

        if(tp == 1) {
            int p,v;
            scanf("%d%d",&p,&v);
            st.update(1,1,m,p,v);
            a[p] = v;

        }  else {
            int l,r,v;
            scanf("%d%d%d",&l,&r,&v);

            pii x = st.query(1,1,m,l,r,in[v],false);
            pii y = st.query(1,1,m,l,r,out[v],true);

            if(x.f == -1) {
                printf("-1 -1\n");
                continue;
            }

            int lca = getLCA(a[x.s],a[y.s]);

            if(lca == v) {
                printf("%d %d\n",min(x.s,y.s),max(x.s,y.s));
            } else {
                printf("-1 -1\n");
            }
        }
    }










}

Compilation message (stderr)

treearray.cpp: In member function 'void segtree::build(int, int, int)':
treearray.cpp:58:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid=b+e>>1;
      |                 ~^~
treearray.cpp: In member function 'std::pair<int, int> segtree::query(int, int, int, int, int, int, bool)':
treearray.cpp:87:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int mid=b+e>>1;
      |                 ~^~
treearray.cpp: In member function 'void segtree::update(int, int, int, int, int)':
treearray.cpp:103:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |         int mid = b + e >> 1;
      |                   ~~^~~
treearray.cpp: In function 'int main()':
treearray.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
treearray.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:138:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         scanf("%d",&tp);
      |         ~~~~~^~~~~~~~~~
treearray.cpp:142:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |             scanf("%d%d",&p,&v);
      |             ~~~~~^~~~~~~~~~~~~~
treearray.cpp:148:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |             scanf("%d%d%d",&l,&r,&v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

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