Submission #1235931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235931		Aviansh	Tourism (JOI23_tourism)	C++20	0 / 100	0 ms	328 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){
        if(up==0){
            return 1;
        }
        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);
    }
};

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--;
    }

    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(n);
    for(int i = m-1;i>=0;i--){
        if(i==m-1){
            rs.update(c[i],c[i],i);
        }
        else{
            rs.update(min(c[i],c[i+1]),max(c[i],c[i+1]),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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41