제출 #1030130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030130		pera	Tourism (JOI23_tourism)	C++17	100 / 100	617 ms	23120 KiB

tourism

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int n , m , q , T = 0;
vector<int> t(N) , C(N) , id(N) , ans(N) , sz(N) , d(N) , up(N) , top(N);
vector<vector<int>> g(N);
vector<vector<pair<int , int>>> query(N);
set<tuple<int , int , int>> S;
void update(int u , int x){
   while(u < N){
      t[u] += x;
      u += u&-u;
   }
}
int get(int u){
   int sum = 0;
   while(u > 0){
      sum += t[u];
      u -= u&-u;
   }
   return sum;
}
void dfs(int u , int p = 1){
   if(u != 1){
      g[u].erase(find(g[u].begin() , g[u].end() , p));
   }
   up[u] = p;
   d[u] = d[p] + 1;
   for(int x = 0;x < (int)g[u].size();x ++){
      dfs(g[u][x] , u);
      sz[u] += sz[g[u][x]];
      if(sz[g[u][0]] < sz[g[u][x]]){
         swap(g[u][0] , g[u][x]);
      }
   }
   ++sz[u];
}
void hld(int u){
   id[u] = ++T;
   for(int x = 0;x < (int)g[u].size();x ++){
      top[g[u][x]] = (x == 0 ? top[u] : g[u][x]);
      hld(g[u][x]);
   }
}
void upd(int l , int r , int x){
   //cout << "make " << l << " " << r << " " << x << endl;
   while(true){
      auto it = S.lower_bound({l , -1 , -1});
      if(it == S.end() || get<0>(*it) < l || get<1>(*it) > r){
         break;
      }
      int L = get<1>(*it) , R = get<0>(*it) , v = get<2>(*it);
      //cout << "xx " << L << " " << R << " " << v << endl;
      S.erase(it);
      update(v , -(min(r , R) - max(L , l) + 1));
      if(L < l){
         S.insert({l - 1 , L , v});
      }
      if(r < R){
         S.insert({R , r + 1 , v});
      }
   }
   S.insert({r , l , x});
   update(x , r - l + 1);
}
void UPD(int u , int v , int x){
   while(top[u] != top[v]){
      //cout << u << " da " << v << endl;
      if(d[top[u]] < d[top[v]]){
         swap(u , v);
      }
      upd(id[top[u]] , id[u] , x);
      u = up[top[u]];
   }
  //cout << u << " das " << v << endl;
   if(d[u] > d[v]){
      swap(u , v);
   }
   upd(id[u] , id[v] , x);
}
int main(){
   cin >> n >> m >> q;
   for(int i = 1;i < n;i ++){
      int u , v;
      cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   dfs(1);
   top[1] = 1;
   hld(1);
   for(int i = 1;i <= m;i ++){
      cin >> C[i];
   }
   for(int i = 1;i <= q;i ++){
      int l , r;
      cin >> l >> r;
      query[r].push_back({l , i});
   }
   for(int i = 1;i <= m;i ++){
      if(i > 1){
         //cout << C[i - 1] << " -> " << C[i] << endl;
         UPD(C[i - 1] , C[i] , i - 1);
      }
      upd(id[C[i]] , id[C[i]] , i);
      for(auto [l , id] : query[i]){
         ans[id] = get(N - 1) - get(l - 1);
      }
   }
   for(int i = 1;i <= q;i ++){
      cout << ans[i] << " ";
   }
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41