Submission #1236151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236151		Aviansh	Tourism (JOI23_tourism)	C++20	100 / 100	623 ms	23624 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

struct FenwickTree{
    vector<int>bit;
    FenwickTree(int n){
        bit = vector<int>(n+1);
    }
    void add(int ind, int val){
        //add value to ind.
        ind++;
        //0 is dummy
        for(;ind<bit.size();ind+=ind&-ind) {bit[ind] += val;}
    }
    int prefSum(int ind){
        ind++;
        int ans = 0;
        for(;ind>0;ind-=ind&-ind) {ans+=bit[ind];}
        return ans;
    }
};

struct rangeStructure{
    //{l,r,number stored}
    set<array<int,3>>rangs;
    FenwickTree fenwick = FenwickTree(1);
    rangeStructure(int n){
        fenwick = FenwickTree(n);
    }

    int pref(int up){
        return fenwick.prefSum(up-1);
    }

    void update(int l, int r, int val){
        while(rangs.size()){
            auto it = rangs.lower_bound({l,-1,-1});
            if(it==rangs.end()){
                it--;
            }
            else if((*it)[0]>r&&it!=rangs.begin()){
                it--;
            }
            //it is to be eliminated.
            int templ = (*it)[0];
            int tempr = (*it)[1];
            int tempv = (*it)[2];
            if(templ>r||tempr<l){
                break;
            }
            rangs.erase(it);
            fenwick.add(tempv,-(tempr-templ+1));
            if(l<=templ&&tempr<=r){
                //do nothing
            }
            else{
                if(templ<l){
                    rangs.insert({templ,l-1,tempv});
                    fenwick.add(tempv,l-templ);
                }
                if(tempr>r){
                    rangs.insert({r+1,tempr,tempv});
                    fenwick.add(tempv,tempr-r);
                }
            }
        }
        rangs.insert({l,r,val});
        fenwick.add(val,r-l+1);
    }
};

void dfs_sz(int st, vector<int>g[], int sz[], int p){
    sz[st]=1;
    for(int i : g[st]){
        if(i==p)
            continue;
        dfs_sz(i,g,sz,st);
        sz[st]+=sz[i];
    }
}
int tim = 0;

void dfs(int st, vector<int>g[], int par, int p[], int tp[], int top, int d[], int dep, int sz[], int id[]){
    tp[st]=top;
    p[st]=par;
    int mxi = -1;
    id[st]=tim++;
    d[st]=dep;
    for(int i : g[st]){
        if(i==par)
            continue;
        if(mxi==-1){
            mxi=i;
        }
        if(sz[i]>sz[mxi]){
            mxi=i;
        }
    }
    if(mxi==-1){
        return;
    }
    dfs(mxi,g,st,p,tp,top,d,dep+1,sz,id);
    for(int i : g[st]){
        if(i==par||i==mxi){
            continue;
        }
        dfs(i,g,st,p,tp,i,d,dep+1,sz,id);
    }
}

void add(int u, int v, rangeStructure &rs, int id[], int p[], int tp[], int d[], int val){
    while(tp[u]!=tp[v]){
        if(d[tp[u]]<d[tp[v]]){
            swap(u,v);
        }
        rs.update(id[tp[u]],id[u],val);
        u=p[tp[u]];
    }
    if(d[u]<d[v]){
        swap(u,v);
    }
    rs.update(id[v],id[u],val);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,q;
    cin >> n >> m >> q;
    vector<int>g[n];
    for(int i = 0;i<n-1;i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int c[m];
    for(int &i : c){
        cin >> i;
        i--;
    }

    int sz[n];

    dfs_sz(0,g,sz,-1);

    int id[n];
    int p[n];
    int tp[n];
    int d[n];

    dfs(0,g,0,p,tp,0,d,0,sz,id);

    vector<array<int,2>>queries[m];
    int ans[q];
    for(int i = 0;i<q;i++){
        int l,r;
        cin >> l >> r;
        l--;r--;
        if(l==r){
            ans[i]=1;
            continue;
        }
        queries[l].push_back({r,i});
    }

    rangeStructure rs(m);

    for(int i = m-1;i>=0;i--){
        if(i==m-1){
            add(c[i],c[i],rs,id,p,tp,d,i);
        }
        else{
            add(c[i],c[i+1],rs,id,p,tp,d,i);
        }
        for(array<int,2>quer:queries[i]){
            ans[quer[1]]=rs.pref(quer[0]);
        }
    }

    for(int i : ans){
        cout << i << "\n";
    }

    return 0;
}

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