Submission #949350

#	Time	Username	Problem	Language	Result	Execution time	Memory
949350		vladilius	Tourism (JOI23_tourism)	C++17	100 / 100	890 ms	25056 KiB

tourism

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct FT{
    vector<int> bit;
    int n;
    FT(int ns){
        n = ns;
        bit.resize(n + 1);
    }
    void upd(int v, int k){
        while (v <= n){
            bit[v] += k;
            v |= (v + 1);
        }
    }
    int get(int v){
        int out = 0;
        while (v > 0){
            out += bit[v];
            v = (v & (v + 1)) - 1;
        }
        return out;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, m, q; cin>>n>>m>>q;
    vector<int> g[n + 1];
    for (int i = 1; i < n; i++){
        int a, b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> c(m + 1);
    for (int i = 1; i <= m; i++){
        cin>>c[i];
    }
    
    vector<int> pos(n + 1), sz(n + 1), p(n + 1), heavy(n + 1), head(n + 1), d(n + 1);
    function<void(int, int)> dfs = [&](int v, int pr){
        p[v] = pr; sz[v] = 1;
        for (int i: g[v]){
            if (i == pr) continue;
            d[i] = d[v] + 1;
            dfs(i, v);
            if (sz[i] > sz[heavy[v]]){
                heavy[v] = i;
            }
            sz[v] += sz[i];
        }
    };
    dfs(1, 0);
    int timer = 0;
    function<void(int, int, int)> dfs_hld = [&](int v, int pr, int k){
        pos[v] = ++timer;
        head[v] = k;
        if (!heavy[v]) return;
        dfs_hld(heavy[v], v, k);
        for (int i: g[v]){
            if (i == pr || i == heavy[v]){
                continue;
            }
            dfs_hld(i, v, i);
        }
    };
    dfs_hld(1, 0, 1);
    
    vector<pii> end[m + 1];
    vector<int> out(q + 1);
    for (int i = 1; i <= q; i++){
        int l, r; cin>>l>>r;
        if (l == r){
            out[i] = 1;
            continue;
        }
        end[l].push_back({r, i});
    }
    
    FT T(m);
    set<array<int, 3>> st;
    auto set = [&](int l, int r, int x){
        while (!st.empty()){
            auto it = st.lower_bound({l, 0, 0});
            if (it == st.end() || (*it)[0] > r) break;
            auto [a, b, k] = *it;
            if (b <= r){
                T.upd(k, -(b - a + 1));
                st.erase(it);
            }
            else {
                T.upd(k, -(r - a + 1));
                st.erase(it);
                st.insert({r + 1, b, k});
            }
        }
        while (!st.empty()){
            auto it = st.upper_bound({l, 0, 0}); 
            if (it == st.begin()) break;
            it--;
            if ((*it)[1] < l) break;
            auto [a, b, k] = *it;
            if (b < r){
                T.upd(k, -(b - l + 1));
                st.erase(it);
                if (a < l) st.insert({a, l - 1, k});
            }
            else {
                T.upd(k, -(r - l + 1));
                st.erase(it);
                if (a < l) st.insert({a, l - 1, k});
                if (r < b) st.insert({r + 1, b});
            }
        }
        T.upd(x, (r - l + 1));
        st.insert({l, r, x});
    };
    auto add = [&](int u, int v, int x){
        while (head[u] != head[v]){
            if (d[head[u]] > d[head[v]]){
                swap(u, v);
            }
            set(pos[head[v]], pos[v], x);
            v = p[head[v]];
        }
        if (d[u] > d[v]) swap(u, v);
        set(pos[u] + 1, pos[v], x);
    };
    
    for (int l = m; l > 0; l--){
        if (l != m){
            add(c[l], c[l + 1], l);
        }
        for (auto [r, j]: end[l]){
            out[j] = T.get(r - 1) + 1;
        }
    }
    for (int i = 1; i <= q; i++){
        cout<<out[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