oj.uz

Submission #730893

# Submission time Handle Problem Language Result Execution time Memory
730893 2023-04-26T15:02:49 Z grogu Passport (JOI23_passport) C++14
16 / 100
 415 ms 786892 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>500){
        cin >> q;
        cin >> q;
        ll i = 1;
        ll ans = 0;
        ll r = a[i].sc;
        while(i!=n){
            ans++;
            ll last = r;
            for(ll j = i;j<=r;j++) r = max(r,a[j].sc);
            i = r;
            if(r==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 404 ms 784692 KB Output is correct
2 Correct 372 ms 784708 KB Output is correct
3 Correct 408 ms 784596 KB Output is correct
4 Incorrect 310 ms 595376 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 377 ms 784652 KB Output is correct
2 Correct 358 ms 784696 KB Output is correct
3 Correct 389 ms 784600 KB Output is correct
4 Correct 399 ms 784712 KB Output is correct
5 Correct 388 ms 784716 KB Output is correct
6 Correct 415 ms 784664 KB Output is correct
7 Correct 367 ms 784724 KB Output is correct
8 Correct 371 ms 784656 KB Output is correct
9 Correct 408 ms 784696 KB Output is correct
10 Correct 404 ms 784732 KB Output is correct
11 Correct 386 ms 786824 KB Output is correct
12 Correct 404 ms 786892 KB Output is correct
13 Correct 394 ms 786892 KB Output is correct
14 Correct 379 ms 786756 KB Output is correct
15 Correct 405 ms 786836 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 784652 KB Output is correct
2 Correct 358 ms 784696 KB Output is correct
3 Correct 389 ms 784600 KB Output is correct
4 Correct 399 ms 784712 KB Output is correct
5 Correct 388 ms 784716 KB Output is correct
6 Correct 415 ms 784664 KB Output is correct
7 Correct 367 ms 784724 KB Output is correct
8 Correct 371 ms 784656 KB Output is correct
9 Correct 408 ms 784696 KB Output is correct
10 Correct 404 ms 784732 KB Output is correct
11 Correct 386 ms 786824 KB Output is correct
12 Correct 404 ms 786892 KB Output is correct
13 Correct 394 ms 786892 KB Output is correct
14 Correct 379 ms 786756 KB Output is correct
15 Correct 405 ms 786836 KB Output is correct
16 Incorrect 286 ms 588628 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 784652 KB Output is correct
2 Correct 358 ms 784696 KB Output is correct
3 Correct 389 ms 784600 KB Output is correct
4 Correct 399 ms 784712 KB Output is correct
5 Correct 388 ms 784716 KB Output is correct
6 Correct 415 ms 784664 KB Output is correct
7 Correct 367 ms 784724 KB Output is correct
8 Correct 371 ms 784656 KB Output is correct
9 Correct 408 ms 784696 KB Output is correct
10 Correct 404 ms 784732 KB Output is correct
11 Correct 386 ms 786824 KB Output is correct
12 Correct 404 ms 786892 KB Output is correct
13 Correct 394 ms 786892 KB Output is correct
14 Correct 379 ms 786756 KB Output is correct
15 Correct 405 ms 786836 KB Output is correct
16 Incorrect 286 ms 588628 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 784692 KB Output is correct
2 Correct 372 ms 784708 KB Output is correct
3 Correct 408 ms 784596 KB Output is correct
4 Incorrect 310 ms 595376 KB Output isn't correct
5 Halted 0 ms 0 KB -