Submission #730886

#	Time	Username	Problem	Language	Result	Execution time	Memory
730886		grogu	Passport (JOI23_passport)	C++14	16 / 100	1097 ms	930624 KiB

passport

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
using namespace std;

#define maxn 5005
#define maxx 200005
#define lg 15
ll n,q;
pll a[maxx];
vector<ll> g[maxn*maxn];
ll dis[maxn*maxn];
ll lg2[maxn];
pll st[lg][maxn];
ll st2[lg][maxn];
ll kod(pll p){return p.fi*(n+1) + p.sc;}
pll rev(ll x){return {x/(n+1),x%(n+1)};}
void upd(ll x,ll y,ll w){
    g[x].pb(y);
    //cerr<<rev(x).fi<< " "<<rev(x).sc<< " "<<rev(y).fi<< " "<<rev(y).sc<<endl;
}
void getdis(ll poc){
    for(ll i = 1;i<maxn*maxn;i++) dis[i] = llinf;
    dis[poc] = 0;
    queue<ll> pq;
    pq.push(poc);
    while(pq.size()){
        ll u = pq.front();
        pq.pop();
        for(ll s : g[u]){
            if(dis[u]+1<dis[s]){
                dis[s] = dis[u] + 1;
                pq.push(s);
            }
        }
    }
}
ll mrg(ll x,ll y){
    if(a[x].sc-a[x].fi>a[y].sc-a[y].fi) return x;
    return y;
}
pll mrg(pll p,pll q){
    pll ans;
    if(a[p.fi].fi<a[q.fi].fi) ans.fi = p.fi;
    else if(a[p.fi].fi==a[q.fi].fi){
        if(a[p.fi].sc>a[q.fi].sc) ans.fi = p.fi;
        else ans.fi = q.fi;
    }else ans.fi = q.fi;
    if(a[p.sc].sc>a[q.sc].sc) ans.sc = p.sc;
    else if(a[p.sc].sc==a[q.sc].sc){
        if(a[p.sc].fi<a[q.sc].fi) ans.sc = p.sc;
        else ans.sc = q.sc;
    }else ans.sc = q.sc;
    return ans;
}
pair<pll,ll> get(ll l,ll r){
    ll len = r-l+1;
    ll x = lg2[len];
    ll len2 = (1<<x);
    pll p = st[x][l];
    pll q = st[x][r-len2+1];
    pll ans = mrg(p,q);
    ll px = st2[x][l];
    ll py = st2[x][r-len2+1];
    ll ansx = mrg(px,py);
    return {ans,ansx};
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	for(ll j = 0;j<lg;j++) if((1<<j)<maxn) lg2[(1<<j)] = j;
	for(ll j = 2;j<maxn;j++){
        if(lg2[j]) continue;
        lg2[j] = lg2[j-1];
	}
    cin >> n;
    for(ll i = 1;i<=n;i++){
        cin >> a[i].fi >> a[i].sc;
        st[0][i] = {i,i};
        st2[0][i] = i;
    }
    if(n>2500){
        cin >> q;
        cin >> q;
        ll i = 1;
        ll ans = 0;
        ll r = a[i].sc;
        while(i!=n){
            ans++;
            ll last = i;
            for(ll j = i;j<=r;j++) i = max(i,a[j].sc);
            if(i==last){
                cout<<-1<<endl;
                return 0;
            }
        }
        cout<<ans<<endl;
        return 0;
    }
    for(ll j = 1;j<lg;j++){
        for(ll i = 1;i<=n;i++){
            if(i+(1<<j)-1>n) continue;
            st[j][i] = mrg(st[j-1][i],st[j-1][i+(1<<(j-1))]);
            st2[j][i] = mrg(st2[j-1][i],st2[j-1][i+(1<<(j-1))]);
        }
    }
    for(ll len = 1;len<=n;len++){
        for(ll i = 1;i+len-1<=n;i++){
            ll l = i,r = i+len-1;
            pair<pll,ll> q = get(l,r);
            upd(kod({l,r}),kod(a[q.sc]),1);
            pll p = q.fi;
            upd(kod({l,r}),kod({a[p.fi].fi,max(r,a[p.fi].sc)}),1);
            upd(kod({l,r}),kod({min(l,a[p.sc].fi),a[p.sc].sc}),1);
        }
    }
    cin >> q;
    while(q--){
        ll x; cin >> x;
        getdis(kod({x,x}));
        ll ans = dis[kod({1,n})];
        if(ans==llinf) cout<<-1<<endl;
        else cout<<ans<<endl;
    }
	return 0;
}
/**
4
1 3
2 4
2 3
4 4
1
1

5
1 5
2 4
2 3
3 5
1 5
1
3

5
1 1
2 3
1 5
3 4
5 5
5
1
2
3
4
5

4
1 2
1 2
3 4
3 4
4
1
2
3
4
**/

• Subtask 1: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46