Submission #653621

#	Time	Username	Problem	Language	Result	Execution time	Memory
653621		pauloamed	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1427 ms	75136 KiB

treearray

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 200000;
const int MAXLOG = 20;

vector<int> g[MAXN];

namespace lca{
  int st[MAXN][MAXLOG], d[MAXN];

  void get_par(int x, int p){
    st[x][0] = p;
    if(p != -1) d[x] = d[p] + 1;
    for(auto y : g[x]) if(y != p) get_par(y, x);
  }

  void init(int root, int n){
    get_par(root, -1);
    for(int l = 1; l < MAXLOG; ++l) for(int i = 0; i < MAXN; ++i){
      if(st[i][l-1] == -1) st[i][l] = -1;
      else st[i][l] = st[st[i][l-1]][l-1];
    }
  }

  int lca(int x, int y){
      if(d[x] < d[y]) swap(x, y);
      int falta_subir = (d[x] - d[y]);
      for(int i = MAXLOG-1; i >= 0; --i) if((1<<i) <= falta_subir){
        falta_subir -= (1<<i);
        x = st[x][i];
      }
      if(x == y) return x;
      for(int i = MAXLOG-1; i >= 0; --i) if(st[x][i] != st[y][i])
        x = st[x][i], y = st[y][i];
      return st[x][0];
  }

  int dist(int a, int b){
    int x = lca(a, b);
    return (d[a] - d[x]) + (d[b] - d[x]);
  }
}

namespace solver{
  int v[2*MAXN];
  set<int> v2pos[MAXN];
  int n;

  void set_val(int i, int x){
    v2pos[v[i]].erase(i);
    v[i] = x;
    v2pos[v[i]].insert(i);
  }

  int get_idx(int i){ return i * 2; }
  void add(int i, int x){
    i = get_idx(i);

    set_val(i, x);

    // for(int j = 0; j <= get_idx(n - 1); ++j){
    //   cout << v[j] << " ";
    // }cout << "\n";

    if(i > 0){
      set_val(i - 1, lca::lca(v[i - 2], v[i]));
    }

    if(i < get_idx(n - 1)){
      set_val(i + 1, lca::lca(v[i], v[i + 2]));
    }
  }

  pair<int,int> query(int l, int r, int x){
    l = get_idx(l);
    r = get_idx(r);

    auto it = v2pos[x].lower_bound(l);
    if(it == v2pos[x].end() || *it > r) return {-1, -1};
    else{
      int i = *it;
      if(*it % 2 == 1){
        return {(i - 1) / 2, (i + 1) / 2};
      }else{
        return {i / 2, i / 2};
      }
    }
  }
}

int main(){
  int n, m, q; cin >> n >> m >> q;
  for(int i = 0; i < n - 1; ++i){
    int a, b; cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  lca::init(0, n);
  solver::n = m;
  for(int i = 0; i <= solver::get_idx(m - 1); ++i){
    solver::v2pos[0].insert(i);
  }

  for(int i = 0; i < m; ++i){
    int x; cin >> x; x--;
    solver::add(i, x);
  }

  for(int i = 0; i < q; ++i){
    int id; cin >> id;
    if(id == 1){
      int i, v; cin >> i >> v;
      i--; v--;
      solver::add(i, v);
    }else{
      int l, r, x; cin >> l >> r >> x;
      l--; r--; x--;
      auto ret = solver::query(l, r, x);
      if(ret.first == -1) cout << "-1 -1\n";
      else{
        cout << ret.first + 1 << " " << ret.second + 1 << "\n";
      }
    }
  }
}

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