oj.uz

Submission #730886

# Submission time Handle Problem Language Result Execution time Memory
730886 2023-04-26T15:00:17 Z grogu Passport (JOI23_passport) C++14
16 / 100
 1097 ms 930624 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 784716 KB Output is correct
2 Correct 341 ms 784724 KB Output is correct
3 Correct 338 ms 784624 KB Output is correct
4 Incorrect 301 ms 595204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 784744 KB Output is correct
2 Correct 371 ms 784700 KB Output is correct
3 Correct 348 ms 784632 KB Output is correct
4 Correct 342 ms 784600 KB Output is correct
5 Correct 338 ms 784676 KB Output is correct
6 Correct 391 ms 784708 KB Output is correct
7 Correct 389 ms 784800 KB Output is correct
8 Correct 355 ms 784716 KB Output is correct
9 Correct 351 ms 784616 KB Output is correct
10 Correct 346 ms 784812 KB Output is correct
11 Correct 366 ms 786656 KB Output is correct
12 Correct 351 ms 786768 KB Output is correct
13 Correct 353 ms 786856 KB Output is correct
14 Correct 361 ms 786740 KB Output is correct
15 Correct 355 ms 786880 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 784744 KB Output is correct
2 Correct 371 ms 784700 KB Output is correct
3 Correct 348 ms 784632 KB Output is correct
4 Correct 342 ms 784600 KB Output is correct
5 Correct 338 ms 784676 KB Output is correct
6 Correct 391 ms 784708 KB Output is correct
7 Correct 389 ms 784800 KB Output is correct
8 Correct 355 ms 784716 KB Output is correct
9 Correct 351 ms 784616 KB Output is correct
10 Correct 346 ms 784812 KB Output is correct
11 Correct 366 ms 786656 KB Output is correct
12 Correct 351 ms 786768 KB Output is correct
13 Correct 353 ms 786856 KB Output is correct
14 Correct 361 ms 786740 KB Output is correct
15 Correct 355 ms 786880 KB Output is correct
16 Correct 952 ms 913808 KB Output is correct
17 Incorrect 1097 ms 930624 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 784744 KB Output is correct
2 Correct 371 ms 784700 KB Output is correct
3 Correct 348 ms 784632 KB Output is correct
4 Correct 342 ms 784600 KB Output is correct
5 Correct 338 ms 784676 KB Output is correct
6 Correct 391 ms 784708 KB Output is correct
7 Correct 389 ms 784800 KB Output is correct
8 Correct 355 ms 784716 KB Output is correct
9 Correct 351 ms 784616 KB Output is correct
10 Correct 346 ms 784812 KB Output is correct
11 Correct 366 ms 786656 KB Output is correct
12 Correct 351 ms 786768 KB Output is correct
13 Correct 353 ms 786856 KB Output is correct
14 Correct 361 ms 786740 KB Output is correct
15 Correct 355 ms 786880 KB Output is correct
16 Correct 952 ms 913808 KB Output is correct
17 Incorrect 1097 ms 930624 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 784716 KB Output is correct
2 Correct 341 ms 784724 KB Output is correct
3 Correct 338 ms 784624 KB Output is correct
4 Incorrect 301 ms 595204 KB Output isn't correct
5 Halted 0 ms 0 KB -