oj.uz

Submission #730888

# Submission time Handle Problem Language Result Execution time Memory
730888 2023-04-26T15:01:13 Z grogu Passport (JOI23_passport) C++14
16 / 100
 1181 ms 930616 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<=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 415 ms 784720 KB Output is correct
2 Correct 354 ms 784716 KB Output is correct
3 Correct 367 ms 784708 KB Output is correct
4 Correct 294 ms 595252 KB Output is correct
5 Incorrect 338 ms 595312 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 371 ms 784612 KB Output is correct
2 Correct 353 ms 784720 KB Output is correct
3 Correct 357 ms 784772 KB Output is correct
4 Correct 350 ms 784692 KB Output is correct
5 Correct 367 ms 784740 KB Output is correct
6 Correct 412 ms 784708 KB Output is correct
7 Correct 385 ms 784672 KB Output is correct
8 Correct 353 ms 784716 KB Output is correct
9 Correct 347 ms 784852 KB Output is correct
10 Correct 413 ms 784652 KB Output is correct
11 Correct 399 ms 786732 KB Output is correct
12 Correct 374 ms 786820 KB Output is correct
13 Correct 395 ms 786864 KB Output is correct
14 Correct 423 ms 786736 KB Output is correct
15 Correct 366 ms 786944 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 784612 KB Output is correct
2 Correct 353 ms 784720 KB Output is correct
3 Correct 357 ms 784772 KB Output is correct
4 Correct 350 ms 784692 KB Output is correct
5 Correct 367 ms 784740 KB Output is correct
6 Correct 412 ms 784708 KB Output is correct
7 Correct 385 ms 784672 KB Output is correct
8 Correct 353 ms 784716 KB Output is correct
9 Correct 347 ms 784852 KB Output is correct
10 Correct 413 ms 784652 KB Output is correct
11 Correct 399 ms 786732 KB Output is correct
12 Correct 374 ms 786820 KB Output is correct
13 Correct 395 ms 786864 KB Output is correct
14 Correct 423 ms 786736 KB Output is correct
15 Correct 366 ms 786944 KB Output is correct
16 Correct 1022 ms 913696 KB Output is correct
17 Incorrect 1181 ms 930616 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 784612 KB Output is correct
2 Correct 353 ms 784720 KB Output is correct
3 Correct 357 ms 784772 KB Output is correct
4 Correct 350 ms 784692 KB Output is correct
5 Correct 367 ms 784740 KB Output is correct
6 Correct 412 ms 784708 KB Output is correct
7 Correct 385 ms 784672 KB Output is correct
8 Correct 353 ms 784716 KB Output is correct
9 Correct 347 ms 784852 KB Output is correct
10 Correct 413 ms 784652 KB Output is correct
11 Correct 399 ms 786732 KB Output is correct
12 Correct 374 ms 786820 KB Output is correct
13 Correct 395 ms 786864 KB Output is correct
14 Correct 423 ms 786736 KB Output is correct
15 Correct 366 ms 786944 KB Output is correct
16 Correct 1022 ms 913696 KB Output is correct
17 Incorrect 1181 ms 930616 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 784720 KB Output is correct
2 Correct 354 ms 784716 KB Output is correct
3 Correct 367 ms 784708 KB Output is correct
4 Correct 294 ms 595252 KB Output is correct
5 Incorrect 338 ms 595312 KB Output isn't correct
6 Halted 0 ms 0 KB -