oj.uz

Submission #730890

# Submission time Handle Problem Language Result Execution time Memory
730890 2023-04-26T15:01:42 Z grogu Passport (JOI23_passport) C++14
16 / 100
 445 ms 786948 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 = i;
            for(ll j = i;j<=a[last].sc;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
**/

Compilation message

passport.cpp: In function 'int main()':
passport.cpp:100:12: warning: unused variable 'r' [-Wunused-variable]
  100 |         ll r = a[i].sc;
      |            ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 784616 KB Output is correct
2 Correct 418 ms 784636 KB Output is correct
3 Correct 362 ms 784608 KB Output is correct
4 Correct 337 ms 595304 KB Output is correct
5 Incorrect 294 ms 595464 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 784660 KB Output is correct
2 Correct 336 ms 784716 KB Output is correct
3 Correct 382 ms 784844 KB Output is correct
4 Correct 336 ms 784648 KB Output is correct
5 Correct 347 ms 784668 KB Output is correct
6 Correct 348 ms 784636 KB Output is correct
7 Correct 351 ms 784708 KB Output is correct
8 Correct 376 ms 784720 KB Output is correct
9 Correct 399 ms 784680 KB Output is correct
10 Correct 387 ms 784616 KB Output is correct
11 Correct 442 ms 786728 KB Output is correct
12 Correct 365 ms 786820 KB Output is correct
13 Correct 445 ms 786948 KB Output is correct
14 Correct 383 ms 786748 KB Output is correct
15 Correct 409 ms 786852 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 784660 KB Output is correct
2 Correct 336 ms 784716 KB Output is correct
3 Correct 382 ms 784844 KB Output is correct
4 Correct 336 ms 784648 KB Output is correct
5 Correct 347 ms 784668 KB Output is correct
6 Correct 348 ms 784636 KB Output is correct
7 Correct 351 ms 784708 KB Output is correct
8 Correct 376 ms 784720 KB Output is correct
9 Correct 399 ms 784680 KB Output is correct
10 Correct 387 ms 784616 KB Output is correct
11 Correct 442 ms 786728 KB Output is correct
12 Correct 365 ms 786820 KB Output is correct
13 Correct 445 ms 786948 KB Output is correct
14 Correct 383 ms 786748 KB Output is correct
15 Correct 409 ms 786852 KB Output is correct
16 Correct 277 ms 588724 KB Output is correct
17 Incorrect 317 ms 588792 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 784660 KB Output is correct
2 Correct 336 ms 784716 KB Output is correct
3 Correct 382 ms 784844 KB Output is correct
4 Correct 336 ms 784648 KB Output is correct
5 Correct 347 ms 784668 KB Output is correct
6 Correct 348 ms 784636 KB Output is correct
7 Correct 351 ms 784708 KB Output is correct
8 Correct 376 ms 784720 KB Output is correct
9 Correct 399 ms 784680 KB Output is correct
10 Correct 387 ms 784616 KB Output is correct
11 Correct 442 ms 786728 KB Output is correct
12 Correct 365 ms 786820 KB Output is correct
13 Correct 445 ms 786948 KB Output is correct
14 Correct 383 ms 786748 KB Output is correct
15 Correct 409 ms 786852 KB Output is correct
16 Correct 277 ms 588724 KB Output is correct
17 Incorrect 317 ms 588792 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 784616 KB Output is correct
2 Correct 418 ms 784636 KB Output is correct
3 Correct 362 ms 784608 KB Output is correct
4 Correct 337 ms 595304 KB Output is correct
5 Incorrect 294 ms 595464 KB Output isn't correct
6 Halted 0 ms 0 KB -