Submission #958750

#	Time	Username	Problem	Language	Result	Execution time	Memory
958750		hotboy2703	Tourism (JOI23_tourism)	C++14	100 / 100	2292 ms	343508 KiB

tourism

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
const ll MAXN = 1e5;
namespace BIT{
    ll a[MAXN + 100];
    void upd(ll i,ll val){
        for (;i <= MAXN;i += i & -i)a[i]+=val;
    }
    ll get(ll i){
        ll res = 0;
        for (;i > 0;i -= i & -i)res += a[i];
        return res;
    }
}
namespace hld{
    ll n;
    vector <ll> g[MAXN+100];
    ll pa[MAXN+100],sz[MAXN+100];
    ll in[MAXN+100],out[MAXN+100];
    ll depth[MAXN+100];
    ll nxt[MAXN+100];
    ll timeDFS;


    void dfs_pa(ll u = 1,ll p = 1){
        pa[u] = p;
        sz[u] = 1;
        depth[u] = depth[p] + 1;
        for (auto v:g[u]){
            if (v==p)continue;
            dfs_pa(v,u);
            sz[u] += sz[v];
        }
    }
    void dfs_hld(ll u = 1){
        in[u] = ++timeDFS;
        for (auto v:g[u]){
            nxt[v] = (v==g[u][0]?nxt[u]:v);
            dfs_hld(v);
        }
        out[u] = timeDFS;
    }


    void init(ll N){
        n = N;
        timeDFS = 0;
        for (ll i = 1;i <= n;i ++)g[i].clear();
        for (ll i = 1;i < n;i ++){
            ll u,v;
            cin>>u>>v;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        dfs_pa();
        for (ll i = 1;i <= n;i ++)g[i].clear();
        for (ll i = 2;i <= n;i ++)g[pa[i]].push_back(i);

        nxt[1] = 1;
        dfs_hld();
//        for (ll i = 1;i <= n;i ++)cout<<pa[i]<<' ';
//        cout<<endl;
//        for (ll i = 1;i <= n;i ++)cout<<nxt[i]<<' ';
//        cout<<endl;
    }

    vector <pll> path(ll u,ll v){
        //pairs of ancestors and successors
        //to get range use in[first] and in[second]
        vector <pll> res;
        while (nxt[u] != nxt[v]){
//            cout<<"WOW "<<u<<' '<<v<<endl;
            if (depth[nxt[u]] > depth[nxt[v]])swap(u,v);
            res.push_back(MP(nxt[v],v));
            v = pa[nxt[v]];
        }
        if (depth[u] > depth[v])swap(u,v);
        res.push_back({u,v});
        return res;
    }
}

//const ll MAXN = 1e5;
ll n,m,q;
ll c[MAXN+100];
//ll range[MAXN+100];
struct range{
    ll l,r,w;
};
vector <range> all;
ll cnt[MAXN+100];
ll ans[MAXN+100];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m>>q;
    hld::init(n);
    for (ll i = 1;i <= m;i ++){
        cin>>c[i];
    }
//    cout<<"OK"<<endl;
    vector <range> sus;
    for (ll i = 1;i + 1 <= m;i ++){
        vector <pll> tmp = hld::path(c[i],c[i+1]);
//        cout<<i<<endl;
        for (auto x:tmp){
//            cout<<x.fi<<' '<<x.se<<endl;
            sus.push_back({hld::in[x.fi],i,1});
            sus.push_back({hld::in[x.se]+1,i,-1});
        }
    }

    sort(sus.begin(),sus.end(),[=](range x, range y){return x.l < y.l;});
//    for (auto x:sus){
//        cout<<x.l<<' '<<x.se<<'\n';
//    }
    set <pll> s({MP(0,1),MP(m,1)});
    for (ll i = 1,ptr = 0;i <= n;i ++){
        vector <pll> all1;
        static bool vis[MAXN+100];
        while (ptr<sz(sus) && sus[ptr].l == i){
            if (!vis[sus[ptr].r]){
                all1.push_back(MP(sus[ptr].r,cnt[sus[ptr].r]));
                vis[sus[ptr].r] = 1;
            }
            cnt[sus[ptr].r] += sus[ptr].w;
            ptr++;
        }
        for (auto x:all1){
            if (vis[x.fi]){
                if (cnt[x.fi] != x.se){
                    if (cnt[x.fi] == 0){
                        auto mid = s.lower_bound(MP(x.fi,0));
                        auto l = prev(mid);
                        auto r = next(mid);
                        all.push_back({(*l).fi + 1,(*mid).fi,(*l).se-i});
                        all.push_back({(*mid).fi + 1,(*r).fi,(*mid).se-i});
                        pll add = MP((*l).fi,i);
                        s.erase(l);
                        s.erase(mid);
                        s.insert(add);
//                        cout<<"WOW "<<endl;
                    }
                    else{
                        auto mid = s.insert(MP(x.fi,i)).fi;
                        auto l = prev(mid);
                        auto r = next(mid);
                        all.push_back({(*l).fi + 1,(*r).fi,(*l).se-i});
                        pll add = MP((*l).fi,i);
                        s.erase(l);
                        s.insert(add);
                    }
                }
                vis[x.fi] = 0;
            }
        }
        if (i == n){
            for (auto it = s.begin();(*it).fi != m;it ++){
                all.push_back({(*it).fi+1,(*next(it)).fi,(*it).se-n-1});
            }
        }
//        for (auto x:s){
//            cout<<x.fi<<' ';
//        }
//        cout<<'\n';
    }
//    cout<<"OK"<<endl;
//    for (auto x:all)cout<<x.l<<' '<<x.r<<' '<<x.w<<'\n';
    sort(all.begin(),all.end(),[](range x,range y){return x.r > y.r;});
    vector <range> query;
    for (ll i = 1;i <= q;i ++){
        ll l,r;
        cin>>l>>r;
        query.push_back({l,r,i});
    }
    sort(query.begin(),query.end(),[](range x,range y){return x.r > y.r;});
    for (ll i = m,ptr1=0,ptr2=0;i >= 1;i --){
        while (ptr1 < sz(all) && all[ptr1].r == i){
            BIT::upd(all[ptr1].l,all[ptr1].w);
            ptr1++;
        }
        while (ptr2 < sz(query) && query[ptr2].r == i){
            ans[query[ptr2].w] = (query[ptr2].l == query[ptr2].r)?1-n:BIT::get(query[ptr2].l);
            ptr2++;
        }
    }
    for (ll i = 1;i <= q;i ++)cout<<(ans[i]+=n)<<'\n';
    cout<<'\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