Submission #1183229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183229		Gray	Passport (JOI23_passport)	C++20	16 / 100	502 ms	1114112 KiB

passport

#ifndef LOCAL
// #pragma GCC optimize("O3,Ofast")
// #pragma GCC target("sse2")
#endif
#include <bits/stdc++.h>
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)

ll n, m, q;
vector<vector<ll>> A;
vector<ll> tin;
vector<ll> smap;

struct Tree{
    vector<vector<pair<ll, ll>>> st;
    vector<ll> level, eid, log;
    vector<pair<ll, ll>> euler;
    void dfs1(ll u, ll p, ll clev, ll &timer){
        tin[u]=timer; timer++; level[u]=clev;
        euler.push_back({clev, u}); eid[u]=euler.size()-1;
        for (auto v:A[u]){
            if (v==p) continue;
            dfs1(v, u, clev+1, timer);
            euler.push_back({clev, u});
        }
    }

    void genST(){
        ll N = euler.size(); log.resize(N+1);
        for (ll i=2; i<=N; i++) log[i]=log[i/2]+1;
        st.resize(log[N]+1, vector<pair<ll, ll>>(N));
        st[0] = euler;
        for (ll i=1; i<=log[N]; i++){
            for (ll j=0; j<=N-(1<<i); j++){
                st[i][j]=min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
            }
        }
    }
    void init(){
        level.resize(n+1); tin.resize(n+1);
        eid.resize(n+1);
        euler.resize(n+1);
        ll timer=0; dfs1(1, 1, 1, timer);
        genST();
    }

    ll lca(ll u, ll v){
        ll l = eid[u], r = eid[v];
        if (l>r) swap(l, r);
        ll lg = log[r-l+1];
        return min(st[lg][l], st[lg][r-(1<<lg)+1]).ss;
    }

    ll dist(ll u, ll v){
        ll lc = lca(u, v);
        return level[u]+level[v]-level[lc]*2;
    }
} tree;

ll pcnt=0;

struct TDist{
    set<pair<ll, ll>> euler;
    vector<ll> cnt; ll dist, l, r;
    TDist(){
        cnt.resize(n+1); dist=0;
        l=-1; r=-1;
    }
    void add(ll u){
        // cout << "added " << u << " -> ";
        cnt[u]++; if (cnt[u]==1){
            if (euler.empty()){
                euler.insert({tin[u], u});
            }else if (euler.size()==1){
                dist+=tree.dist(u, (*euler.begin()).ss);
                euler.insert({tin[u], u});
            }else{
                auto iter = euler.upper_bound({tin[u], u});
                if (iter==euler.end()){
                    iter--; dist-=tree.dist((*euler.begin()).ss, tree.lca((*euler.begin()).ss, (*iter).ss));
                    dist+=tree.level[u]-tree.level[tree.lca(u, (*iter).ss)];
                    dist+=tree.level[(*euler.begin()).ss]-tree.level[tree.lca(u, (*euler.begin()).ss)];
                    euler.insert({tin[u], u});
                }else if (iter==euler.begin()){
                    dist-=tree.dist((*iter).ss, tree.lca((*euler.rbegin()).ss, (*iter).ss));
                    dist+=tree.level[u]-tree.level[tree.lca(u, (*euler.rbegin()).ss)];
                    dist+=tree.level[(*iter).ss]-tree.level[tree.lca(u, (*iter).ss)];
                    euler.insert({tin[u], u});
                }else{
                    auto piter=iter; piter--;
                    dist-=tree.level[(*iter).ss]-tree.level[tree.lca((*iter).ss, (*piter).ss)];
                    dist+=tree.level[(*iter).ss]-tree.level[tree.lca((*iter).ss, u)];
                    dist+=tree.level[u]-tree.level[tree.lca(u, (*piter).ss)];
                    euler.insert({tin[u], u});
                }
            }
        }
        // cout << dist << ln;
    }
    void remove(ll u){
        // cout << "removed " << u << " -> ";
        cnt[u]--; if (cnt[u]==0){
            if (euler.size()==1){
                euler.erase(euler.begin());
            }else if (euler.size()==2){
                dist-=tree.dist((*euler.begin()).ss, (*euler.rbegin()).ss);
                euler.erase({tin[u], u});
            }else{
                auto iter = euler.find({tin[u], u});
                ll pu, nu;
                if (iter==euler.begin()){
                    iter++; pu = (*euler.rbegin()).ss; nu = (*iter).ss;
                }else if ((*iter)==(*euler.rbegin())){
                    iter--; pu = (*iter).ss; nu = (*euler.begin()).ss;
                }else{
                    iter--; pu = (*iter).ss; iter++;
                    iter++; nu = (*iter).ss;
                }
                dist-=tree.level[u]-tree.level[tree.lca(pu, u)];
                dist-=tree.level[nu]-tree.level[tree.lca(u, nu)];
                dist+=tree.level[nu]-tree.level[tree.lca(pu, nu)];
                euler.erase({tin[u], u});
            }
        }
        // cout << dist << ln;
    }
    void shift(ll tl, ll tr){
        if (l==-1 and r==-1){
            l=tl; r=tr;
            for (ll i=l; i<=r; i++) add(smap[i]);
        }else{
            while (l>tl){
                pcnt++;
                l--; add(smap[l]);
            }
            while (r<tr){
                pcnt++;
                r++; add(smap[r]);
            }
            while (l<tl){
                pcnt++;
                remove(smap[l]); l++;
            }
            while (r>tr){
                pcnt++;
                remove(smap[r]); r--;
            }
        }
    }
};

ll B = 400;

void solve(){
    cin >> n >> m >> q; A.resize(n+1);
    for (ll i=0; i<n-1; i++){
        ll u, v; cin >> u >> v;
        A[u].push_back(v); A[v].push_back(u);
    }
    tree.init(); smap.resize(m);
    for (ll i=0; i<m; i++) cin >> smap[i];
    vector<pair<ll, ll>> qs(q);
    vector<pair<pair<ll, ll>, ll>> sqs(q);
    for (ll i=0; i<q; i++){
        cin >> qs[i].ff >> qs[i].ss; qs[i].ff--; qs[i].ss--;
        sqs[i] = {qs[i], i};
    }
    TDist tdist; vector<ll> crng;
    vector<ll> res(q);

    sort(sqs.begin(), sqs.end(), [&](auto op1, auto op2){
        if (op1.ff.ff/B==op2.ff.ff/B) return op1.ff.ss<op2.ff.ss;
        return op1.ff.ff/B<op2.ff.ff/B;
    });
    for (auto [rng, i]:sqs){
        tdist.shift(rng.ff, rng.ss); res[i] = tdist.dist;
    }
    // cout << pcnt << " - " << B << ln;
    for (ll i=0; i<q; i++){
        cout << res[i]+1 << ln;
    }
}


struct ST{
    vector<vector<pair<ll, ll>>> stMN, stMX;
    vector<ll> log; ll N;
    void init(ll _n, vector<pair<ll, ll>> &a){
        N=_n; log.resize(N+1);
        for (ll i=2; i<=N; i++) log[i]=log[i/2]+1;
        stMN.resize(log[N]+1, vector<pair<ll, ll>>(N));
        stMX.resize(log[N]+1, vector<pair<ll, ll>>(N));
        stMN[0]=stMX[0]=a;
        for (ll i=1; i<=log[N]; i++){
            for (ll j=0; j<=(N-(1<<i)); j++) {
                stMN[i][j]=min(stMN[i-1][j], stMN[i-1][j+(1<<(i-1))]);
                stMX[i][j]=max(stMX[i-1][j], stMX[i-1][j+(1<<(i-1))]);
            }
        }
    }
    pair<ll, ll> queryMN(ll l, ll r){
        ll lg = log[r-l+1];
        // for (auto ch:stMN[0]) cout << ch.ff << " ";
        pair<ll, ll> res = min(stMN[lg][l], stMN[lg][r-(1<<lg)+1]);
        // cout << " L -> " << res.ff << ln;
        return res;
    }
    pair<ll, ll> queryMX(ll l, ll r){
        ll lg = log[r-l+1];
        // for (auto ch:stMX[0]) cout << ch.ff << " ";
        pair<ll, ll> res=max(stMX[lg][l], stMX[lg][r-(1<<lg)+1]);
        // cout << " R " << l << "-" << r << " -> " << res.ff << ln;
        return res;
    }
};


vector<vector<ll>> dp;
vector<vector<ll>> proc;
vector<pair<ll, ll>> ls, rs;
ST mns, mxs;
ll rec(ll l, ll r){
    // cout << l << " - " << r << ln;
    if (l==0 and r==n-1){
        return 1;
    }else{
        if (!proc[l][r]){
            ll mnl = mns.queryMN(l, r).ss;
            ll mxr = mxs.queryMX(l, r).ss;
            // cout << mnl << " & " << mxr << ln;
            if (ls[mnl].ff<l or rs[mnl].ff>r) dp[l][r] = min(dp[l][r], rec(min(l, ls[mnl].ff), max(r, rs[mnl].ff))+1);
            if (ls[mxr].ff<l or rs[mxr].ff>r) dp[l][r] = min(dp[l][r], rec(min(l, ls[mxr].ff), max(r, rs[mxr].ff))+1);
            proc[l][r]=1;
        }
        return dp[l][r];
    }
}

void gave_up(){
    cin >> n; vector<pair<ll, ll>> rng(n);
    ls.resize(n); rs.resize(n);
    dp.resize(n, vector<ll>(n, INF));
    proc.resize(n, vector<ll>(n, 0));
    for (ll i=0; i<n; i++){
        cin >> rng[i].ff >> rng[i].ss; rng[i].ff--; rng[i].ss--;
        ls[i]={rng[i].ff, i}; rs[i]={rng[i].ss, i};
    }
    mns.init(n, ls); mxs.init(n, rs);
    cin >> q;
    while (q--){
        ll x; cin >> x; x--;
        ll res=rec(rng[x].ff, rng[x].ss);
        cout << (res>=INF?-1:res) << 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++) gave_up();
    #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: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46