Submission #1190398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190398		TsotneSV	Tourism (JOI23_tourism)	C++20	Compilation error	0 ms	0 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⠀⠀⠀⠀⠀⠀⠀⡄⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⠛⣿⠀⠀⠀⠀⣤⣿⢻⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣤⣿⡛⠀⣤⣿⣿⣤⣤⣿⣿⣤⢸⡇⠀
⠀⠀⠀⠀⠀⠀⠀⠀⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀
⠀⠀⠀⠀⠀⠀⠀⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡗⠀
⢠⣼⣿⣿⣿⣿⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷
⢸⣿⣿⡟⠛⠛⢿⣿⣿⣿⣿⣿⣿⣿⣤⣤⣤⣿⣿⣿⣿⣤⣤⣼⣿⣿
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠛⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠋       
*/
#define fi first
#define se second
#define pb push_back
#define ins insert
#define sz(a) (int)(a.size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

//#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

//const int mod = 1e9+7;
//const int mod = 998244353;
const int MAXN=1e5+5; 
const ll inf=1e9,INF=1e18; 


struct BIT {
    int n; vector<long long> S;

    void update(int pos,int add) {
        for(pos;pos<=n;pos+=pos&-pos) S[pos]+=add;
    }

    ll sum(int pos) {
        ll ret=0;
        for(pos;pos>0;pos-=pos&-pos) ret += S[pos];
        return ret;
    }

    ll query(int l,int r) {
        return sum(r) - sum(l-1);
    }

    BIT() {}

    BIT(int n) {
        this->n = n;
        S = vector<long long>(n+1,0);
    }


};

int n,m,q,C[MAXN],ans[MAXN],subtr[MAXN],id[MAXN],tp[MAXN],depth[MAXN],par[MAXN];
array<int,3> Q[MAXN];
vi g[MAXN];
int t = 1;
BIT ds;

int dfs_util(int v,int p = 0) {

    subtr[v] = 1; depth[v] = depth[p] + 1; par[v] = p;

    for(int i : g[v]) {
        if(i == p) continue;
        subtr[v] += dfs_util(i,v);
    }

    return subtr[v];
}

void dfs_init(int v,int p = 0,int top = 1) {

    tp[v] = top;
    id[v] = t++; 

    int hc = -1;

    for(int i : g[v]) {
        if(i == p) continue;
        if(hc == -1 or subtr[i] > subtr[hc]) hc = i;
    }

    if(hc == -1) return;

    dfs_init(hc,v,top);

    for(int i : g[v]) {
        if(i == p or i == hc) continue;
        dfs_init(i,v,i);
    }

}

set<array<int,3>> st;

void upd(int l,int r,int x) {

    ds.update(x,r-l+1);

    auto p = st.lower_bound({l,0,0});

    if(p != st.begin()) {
        p--; auto [tl,tr,tx] = *p;

        if(tr >= l) {
            st.erase(p); ds.update(tx,-min(r,tr)+l-1);
            st.ins({tl,l-1,tx});
            if(tr > r) st.ins({r+1,tr,tx});
        }

        p = st.lower_bound({l,0,0});
    }

    while(p != st.end()) {
        auto [tl,tr,tx] = *p;
        if(tl > r) break;

        st.erase(p); ds.update(tx,-min(r,tr)+tl-1);
        if(tr > r) st.ins({r+1,tr,tx});
        
        p = st.upper_bound({tl,tr,tx});
    }

    st.ins({l,r,x});

}

void update(int u,int v,int x) {

    while(tp[u] != tp[v]) {
        if(depth[tp[u]] < depth[tp[v]]) swap(u,v);
        upd(id[tp[u]],id[u],x);
        u = par[tp[u]];
    }

    if(depth[u] < depth[v]) swap(u,v);
    upd(id[v],id[u],x);

}

void solve(int tc = 0){
    cin>>n>>m>>q; depth[0] = 0;

    for(int i=0;i<n-1;i++) {
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }

    dfs_util(1);
    dfs_init(1);

    for(int i=1;i<=m;i++) cin>>C[i];
    for(int i=1;i<=q;i++) cin>>Q[i][0]>>Q[i][1],Q[i][2]=i;
    sort(Q+1,Q+q+1,[&](auto &a,auto &b){return a[0] > b[0];});


    int c_l = m+1; ds = BIT(m);

    for(int i=1;i<=q;i++) { 

        auto [L,R,eid] = Q[i];

        if(L == R) {
            ans[eid] = 1;
            continue;
        }

        while(c_l > L) {
            c_l--;
            if(c_l == m) continue;
            update(C[c_l],C[c_l+1],c_l+1);
        }

        ans[eid] = ds.sum(R);

    }

    for(int i=1;i<=q;i++) print(ans[i]);
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    solve();
}

Compilation message (stderr)

tourism.cpp:27:10: fatal error: debug.h: No such file or directory
   27 | #include "debug.h"
      |          ^~~~~~~~~
compilation terminated.