Submission #1185384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185384		Gray	Tourism (JOI23_tourism)	C++20	100 / 100	1061 ms	32848 KiB

tourism

#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

struct Fenwick{
    vector<ll> tr; ll n, offs;
    Fenwick(ll N){
        offs=10; n=N+20; tr.resize(n+1);
    }
    void add(ll i, ll x){
        // cout << "ADD " << i << " <- " << x << ln;
        i+=offs;
        for (; i; i-=(-i&i)) tr[i]+=x;
    }
    ll get(ll i){
        // cout << "Querying " << i << " -> ";
        ll sum=0; i+=offs;
        for (; i<=n; i+=(-i&i)) sum+=tr[i];
        // cout << sum << ln;
        return sum;
    }
};

struct SegTree{
    struct node{
        ll val, orig, upd;
    };
    vector<node> t;
    ll rsz, sz;
    void init(ll N){
        t.resize(N*4, {0, 1, 0});
        sz=N*4; rsz=N;
    }
    void preprocess(ll tl, ll tr, ll v){
        if (t[v].upd){
            t[v].val=t[v].upd; t[v].orig=1;
            if (tl!=tr){
                t[v*2].upd=t[v*2+1].upd=t[v].upd;
            }
            t[v].upd=0;
        }
    }
    node merge(node l, node r){
        return {l.val, (l.val==r.val and l.orig and r.orig), 0};
    }
    void update(ll tl, ll tr, ll v, ll l, ll r, ll x, Fenwick &wr){
        preprocess(tl, tr, v);
        assert(tl!=tr or t[v].orig);
        if (l<=tl and tr<=r and t[v].orig){
            wr.add(t[v].val, -(tr-tl+1)); t[v].upd = x;
            wr.add(x, tr-tl+1); preprocess(tl, tr, v);
        }else if (tr<l or r<tl or (t[v].orig and t[v].val==x)){
            return;
        }else{
            ll tm = (tl+tr)/2;
            update(tl, tm, v*2, l, r, x, wr);
            update(tm+1, tr, v*2+1, l, r, x, wr);
            t[v]=merge(t[v*2], t[v*2+1]);
        }
    }
    void update(ll l, ll r, ll x, Fenwick &wr){
        // cout << "ENTERED" << endl;
        if (l>r) swap(l, r);
        update(0, rsz-1, 1, l, r, x, wr);
        // cout << "Exited" << endl;
    }
};

ll n, m, q;
vector<vector<ll>> A;
struct HLD{
    vector<ll> par, level, nxt, eid, sz;
    SegTree tr;
    void dfs1(ll u, ll p, ll clev){
        par[u]=p; level[u]=clev; sz[u]=1;
        ll mxsz=0;
        for (auto &v:A[u]){
            if (v==p) continue;
            dfs1(v, u, clev+1); sz[u]+=sz[v];
            if (sz[v]>mxsz){
                swap(A[u][0], v); mxsz=sz[v];
            }
        }
    }
    void dfs2(ll u, ll p, ll &timer){
        eid[u]=timer; timer++;
        bool first=1;
        for (auto v:A[u]){
            if (v==p) continue;
            if (first){
                nxt[v]=nxt[u]; first=0;
            }else nxt[v]=v;
            dfs2(v, u, timer);
        }
    }
    HLD(){
        par.resize(n+1); level.resize(n+1);
        nxt.resize(n+1); eid.resize(n+1); sz.resize(n+1);
        dfs1(1, 1, 1); nxt[1]=1; ll timer=0; dfs2(1, 1, timer);
        tr.init(timer);
    }
    void update(ll u, ll v, ll x, Fenwick &wr){
        // cout << "Updating------------------: " << u << "-" << v << ln;
        while (nxt[u]!=nxt[v]){
            if (level[nxt[u]]<level[nxt[v]]) swap(u, v);
            // cout << u << "-" << nxt[u] << " upd " << x << ln;
            tr.update(eid[u], eid[nxt[u]], x, wr);
            u=par[nxt[u]];
        }
        // if (u!=v){
            // cout << u << "-" << v << " upd " << x << ln;
            tr.update(eid[u], eid[v], x, wr);
        // }
        // cout << "Finished" << ln;
    }
};


void solve(){
    cin >> n >> m >> q; A.resize(n+1);
    for (ll i=1; i<n; i++){
        ll u, v; cin >> u >> v;
        A[u].push_back(v); A[v].push_back(u);
    }
    vector<ll> a(m+1);
    for (ll i=1; i<=m; i++) cin >> a[i];
    vector<vector<pair<ll, ll>>> qs(m+1);
    for (ll i=0; i<q; i++){
        ll l, r; cin >> l >> r; qs[r].push_back({l, i});
    }
    vector<ll> res(q, 1);
    HLD ds; Fenwick tr(m+1);
    for (ll i=2; i<=m; i++){
        ds.update(a[i], a[i-1], i, tr);
        for (auto [l, j]:qs[i]){
            if (l!=i) res[j]=tr.get(l+1);
        }
    }
    for (ll i=0; i<q; i++) cout << res[i] << ln;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll __c=1; __c<=t; __c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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