Submission #999165

#	Time	Username	Problem	Language	Result	Execution time	Memory
999165		imarn	Tourism (JOI23_tourism)	C++14	100 / 100	255 ms	25808 KiB

tourism

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
using namespace std;
const int mxn=1e5+5,blc=1200;
vector<int>g[mxn];
int fw[mxn]{0};
void add(int i,int amt){
    for(;i<mxn;i+=i&-i)fw[i]+=amt;
}
int get(int i,int res=0){
    for(;i;i-=i&-i)res+=fw[i];
    return res;
}
struct node{
    int l,r,id;
    bool operator<(const node &o)const{
        return l<o.l;
    }
};
multiset<node>ms[mxn];
int tin[mxn],cnt=0,pr[mxn],d[mxn]{0},sz[mxn],head[mxn];
void dfssz(int u,int p,int l){
    d[u]=l;sz[u]=1;pr[u]=p;
    for(auto v:g[u]){
        if(v==p)continue;
        dfssz(v,u,l+1);sz[u]+=sz[v];
    }
}
void hld(int u,int p,int tp){
    head[u]=tp;int hv=-1;tin[u]=++cnt;
    for(auto v:g[u]){
        if(v==p)continue;
        if(hv==-1||sz[v]>sz[hv])hv=v;
    }if(hv==-1)return;
    hld(hv,u,tp);
    for(auto v:g[u]){
        if(v==p||v==hv)continue;
        hld(v,u,v);
    }
}
void update(int u,int v,int id){
    while(head[u]!=head[v]){
        if(d[head[u]]<d[head[v]])swap(u,v);
        node x={tin[head[u]],tin[u],id};
        while(!ms[head[u]].empty()){
            node it = *ms[head[u]].begin();
            if(x.r<it.l)break;
            add(it.id,-(it.r-it.l+1));
            ms[head[u]].erase(it);
            if(it.r>x.r){
                it.l=x.r+1;
                add(it.id,it.r-it.l+1);
                ms[head[u]].insert(it);
            }
        }add(x.id,x.r-x.l+1);ms[head[u]].insert(x);u=pr[head[u]];
    }if(d[u]>d[v])swap(u,v);
    node x={tin[u],tin[v],id};
    while(!ms[head[u]].empty()){
        auto ij = ms[head[u]].upper_bound(x);
        if(ij==ms[head[u]].begin())break;
        node it = *(--ij);
        if(it.r<x.l)break;
        add(it.id,-(it.r-it.l+1));
        ms[head[u]].erase(it);
        if(x.r<it.r){
            node y=it;
            y.l=x.r+1;
            add(it.id,y.r-y.l+1);
            ms[head[u]].insert(y);
        }
        if(it.l<x.l){
            node y=it;
            y.r=x.l-1;
            add(it.id,y.r-y.l+1);
            ms[head[u]].insert(y);
        }
    }
    while(!ms[head[u]].empty()){
        auto ij = ms[head[u]].lower_bound(x);
        if(ij==ms[head[u]].end())break;
        node it=*ij;
        if(x.r<it.l)break;
        add(it.id,-(it.r-it.l+1));
        ms[head[u]].erase(it);
        if(x.r<it.r){
            node y=it;
            y.l=x.r+1;
            add(it.id,y.r-y.l+1);
            ms[head[u]].insert(y);
        }
    }add(x.id,x.r-x.l+1);ms[head[u]].insert(x);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=n-1;i++){
        int u,v;cin>>u>>v;g[u].pb(v),g[v].pb(u);
    }dfssz(1,1,0);hld(1,1,0);int a[m+1];
    for(int i=1;i<=m;i++)cin>>a[i];
    vector<pii>qr[m+1];int ans[q+1];
    for(int i=1;i<=q;i++){
        int l,r;cin>>l>>r;
        if(l==r)ans[i]=1;
        else qr[r].pb({l,i});
    }
    for(int i=2;i<=m;i++){
        update(a[i-1],a[i],i);
        for(auto it:qr[i]){
            ans[it.s]=get(i)-get(it.f);
        }
    }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