Submission #787080

#	Time	Username	Problem	Language	Result	Execution time	Memory
787080		fuad27	Tourism (JOI23_tourism)	C++17	100 / 100	806 ms	26124 KiB

tourism

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int N=1e5+10;
int n, m, q, sz[N];
vector<int> g[N];
int id[N], tp[N], par[N], depth[N];
struct node {
  int l, r;
  int val;
  bool operator<(const node& B) const {
    return l<B.l;
  }
};
int fen[N+10];
void upd(int at, int val) {
  at++;
  while(at<N) {
    fen[at]+=val;
    at+=at&(-at);
  }
}
int que(int at) {
  int res=0;
  at++;
  while(at) {
    res+=fen[at];
    at-=at&(-at);
  }
  return res;
}
set<node> s;
auto split(int x) {
  auto it=--s.upper_bound(node({x,0,0}));
  if(it->l==x)return it;
  if(it->r<x)return s.end();
  int l=it->l, r=it->r, val = it->val;
  s.erase(it);
  s.insert({l, x-1, val});
  return s.insert({x, r, val}).first;
}
void update(int l, int r, int val) {
  auto it2=split(r+1), it1=split(l);
  for(auto it=it1;it!=it2;it++) {
    upd(it->val, -(it->r-it->l+1));
  }
  s.erase(it1, it2);
  s.insert({l, r, val});
  upd(val, r-l+1);
}
int C=1;
void dfs_sz(int at, int p) {
  sz[at]=1;
  for(int to:g[at]) {
    if(to==p)continue;
    depth[to]=depth[at]+1;
    dfs_sz(to,at);
    sz[at]+=sz[to];
  }
}
void dfs(int at, int p, int top) {
  id[at]=C++;
  tp[at]=top;
  par[at]=p;
  int hv_child=-1, hv_sz=-1;
  for(int to:g[at]) {
    if(to==p)continue;
    if(sz[to]>hv_sz) {
      hv_child=to;
      hv_sz=sz[to];
    }
  }
  if(hv_child==-1)return;
  dfs(hv_child, at, top);
  for(int to:g[at]) {
    if(to==p or to==hv_child)continue;
    dfs(to, at, to);
  }
}
void queryy(int x, int y, int val) {
  while(tp[x]!=tp[y]) {
    if(depth[tp[x]]<depth[tp[y]])swap(x,y);
    update(id[tp[x]], id[x], val);
    x=par[tp[x]];
  }
  if(depth[x]>depth[y])swap(x,y);
  update(id[x], id[y], val);
}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> q;
  for(int i = 1;i<n;i++) {
    int A, B;
    cin >> A >> B;
    g[A].push_back(B);
    g[B].push_back(A);
  }
  for(int i = 0;i<n+10;i++)s.insert({i,0,0});
  upd(0, n+10);
  dfs_sz(1,1);
  dfs(1,1,1);
  int c[m+1];
  for(int i = 1;i<=m;i++)cin >> c[i];
  vector<pair<int,int>> quee[m+1];
  int ress[q];
  for(int i = 0;i<q;i++) {
    int l, r;
    cin >> l >> r;
    quee[r].push_back({l, i});
  }
  for(int i = 1;i<=m;i++) {
    if(i>1)queryy(c[i], c[i-1], i);
    for(auto j:quee[i]) {
      if(j.first!=i) {
        ress[j.second]=que(m+10)-que(j.first);
      }
      else ress[j.second]=1;
    }
  }
  for(int i = 0;i<q;i++)cout << ress[i] << "\n";
}

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