Submission #1212307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212307		VMaksimoski008	Tourism (JOI23_tourism)	C++20	100 / 100	604 ms	18288 KiB

tourism

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

const int N = 1e5 + 5;

struct fenwick {
    int n;
    vector<int> tree;

    fenwick(int _n) : n(_n+10), tree(n+50) {}

    void update(int p, int v) {
        for(p++; p; p-=p&-p) tree[p] += v;
    }

    int query(int p) {
        int ans = 0;
        for(p++; p<n; p+=p&-p) ans += tree[p];
        return ans;
    }
} fwt(N);

set<ar<int, 3> > st;
int par[N], top[N], in[N], sub[N], dep[N], timer = 1, n, m, q;
vector<int> g[N];

int dfs(int u, int p) {
    sub[u] = 1;
    par[u] = p;
    dep[u] = dep[p] + 1;
    for(int v : g[u]) if(v ^ p) sub[u] += dfs(v, u);
    return sub[u];
}

void hld(int u, int p, int h) {
    top[u] = h;
    in[u] = timer++;

    int ch = 0;
    for(int v : g[u])
        if(v != p && sub[v] > sub[ch]) ch = v;
    
    if(ch) hld(ch, u, h);
    for(int v : g[u])
        if(v != p && v != ch) hld(v, u, v);
}

void work(int l, int r, int w) {
    while(true) {
        auto it = st.lower_bound({ l, 0, 0 });
        if(it == st.end() || it->at(0) < l || it->at(1) > r) break;
        auto [r2, l2, w2] = *it;
        st.erase(it);

        fwt.update(w2, max(l, l2) - min(r, r2) - 1);
        if(l2 < l) st.insert({ l-1, l2, w2 });
        if(r2 > r) st.insert({ r2, r+1, w2 });
    }
    
    st.insert({ r, l, w });
    fwt.update(w, r-l+1);
}

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

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(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);
    }

    dfs(1, 0);
    hld(1, 0, 1);

    vector<pair<int, int> > qus[m+1];
    vector<int> a(m+1), ans(q+1, 1);
    for(int i=1; i<=m; i++) cin >> a[i];

    for(int i=1; i<=q; i++) {
        int l, r; cin >> l >> r;
        if(l < r) qus[r].push_back({ l, i });
    }

    for(int r=1; r<=m; r++) {
        if(r > 1) upd(a[r-1], a[r], r-1);
        for(auto [l, id] : qus[r]) ans[id] = fwt.query(l);
    }

    for(int i=1; i<=q; i++) cout << ans[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