Submission #1157517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157517		dombly	Tourism (JOI23_tourism)	C++20	31 / 100	825 ms	24136 KiB

tourism

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int inf = 1e8;

set<array<int,3>>st;
vector<int>g[N];
vector<pair<int,int>>kveri[N];
int a[N],in[N],siz[N],top[N],dep[N],timer = 0,fenw[N],par[N],ans[N];

void add(int i,int n,int x) {
    for(;i <= n; i += (i & -i)) fenw[i] += x;
}

int get(int i) {
    int res = 0;
    for(; i >= 1; i -= (i & -i)) res += fenw[i];
    return res;
}

void dfs(int x,int p) {
    par[x] = p;
    in[x] = ++timer;
    siz[x] = 1;
    for(int j : g[x]) {
        if(j != p) {
            dep[j] = dep[x] + 1;
            dfs(j,x);
            siz[x] += siz[j];
        }
    }
}

void build(int x,int p,int tp) {
    top[x] = tp;
    int mx = 0,idx = 0;
    for(int j : g[x]) {
        if(j != p) {
            if(siz[j] > mx) {
                mx = siz[j];
                idx = j;
            }
        }
    }
    if(mx == 0) return;
    build(idx,x,tp);
    for(int j : g[x]) {
        if(j != p && j != idx) build(j,x,j);
    }
}

void update(int l,int r,int v) {
    if(l > r) swap(l,r);
    auto lb = st.lower_bound({l,0,0});
    vector<array<int,3>>vec;
    if(lb != st.begin()) {
        vec.pb(*prev(lb));
    }
    while(lb != st.end()) {
        array<int,3>u = *lb;
        if(u[0] > r) break;
        vec.pb(u);
        lb++;
    }
    for(auto [ll,rr,vv] : vec) {
        if(rr < l || ll > r) continue;
        add(vv,N - 1,-(min(rr,r) - max(ll,l) + 1));
        if(ll < l) st.insert({ll,l - 1,vv});
        if(rr > r) st.insert({r + 1,rr,vv});
        st.erase({ll,rr,vv});
    }
    add(v,N - 1,r - l + 1);
    st.insert({l,r,v});
}

void modify(int u,int v,int w) {
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u,v);
        update(in[top[u]],in[u],w);
        u = par[top[u]];
    }
    update(in[u],in[v],w);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m,q;
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++) {
        int u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i = 1; i <= m; i++) cin >> a[i];
    for(int i = 1; i <= q; i++) {
        int l,r;
        cin >> l >> r;
        kveri[r].pb({l,i});
    }
    dfs(1,0);
    build(1,0,1);
    for(int i = 1; i <= m; i++) {
        if(i > 1) modify(a[i - 1],a[i],i - 1);
        for(auto x : kveri[i]) {
            if(x.F == i) ans[x.S] = 1;
            else ans[x.S] = get(N - 1) - get(x.F - 1);
        }
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
    return 0;
}

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