oj.uz

Submission #730878

# Submission time Handle Problem Language Result Execution time Memory
730878 2023-04-26T14:50:42 Z grogu Passport (JOI23_passport) C++14
16 / 100
 1071 ms 930628 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 lg 15
ll n,q;
pll a[maxn];
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++) 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;
    }
    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
**/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 784940 KB Output is correct
2 Correct 335 ms 784700 KB Output is correct
3 Correct 361 ms 784712 KB Output is correct
4 Runtime error 672 ms 912784 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 784660 KB Output is correct
2 Correct 378 ms 784724 KB Output is correct
3 Correct 355 ms 784824 KB Output is correct
4 Correct 361 ms 784788 KB Output is correct
5 Correct 384 ms 784668 KB Output is correct
6 Correct 354 ms 784704 KB Output is correct
7 Correct 339 ms 784708 KB Output is correct
8 Correct 375 ms 784716 KB Output is correct
9 Correct 354 ms 784732 KB Output is correct
10 Correct 343 ms 784840 KB Output is correct
11 Correct 383 ms 786700 KB Output is correct
12 Correct 366 ms 786852 KB Output is correct
13 Correct 356 ms 786948 KB Output is correct
14 Correct 347 ms 786792 KB Output is correct
15 Correct 411 ms 787004 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 784660 KB Output is correct
2 Correct 378 ms 784724 KB Output is correct
3 Correct 355 ms 784824 KB Output is correct
4 Correct 361 ms 784788 KB Output is correct
5 Correct 384 ms 784668 KB Output is correct
6 Correct 354 ms 784704 KB Output is correct
7 Correct 339 ms 784708 KB Output is correct
8 Correct 375 ms 784716 KB Output is correct
9 Correct 354 ms 784732 KB Output is correct
10 Correct 343 ms 784840 KB Output is correct
11 Correct 383 ms 786700 KB Output is correct
12 Correct 366 ms 786852 KB Output is correct
13 Correct 356 ms 786948 KB Output is correct
14 Correct 347 ms 786792 KB Output is correct
15 Correct 411 ms 787004 KB Output is correct
16 Correct 984 ms 913928 KB Output is correct
17 Incorrect 1071 ms 930628 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 784660 KB Output is correct
2 Correct 378 ms 784724 KB Output is correct
3 Correct 355 ms 784824 KB Output is correct
4 Correct 361 ms 784788 KB Output is correct
5 Correct 384 ms 784668 KB Output is correct
6 Correct 354 ms 784704 KB Output is correct
7 Correct 339 ms 784708 KB Output is correct
8 Correct 375 ms 784716 KB Output is correct
9 Correct 354 ms 784732 KB Output is correct
10 Correct 343 ms 784840 KB Output is correct
11 Correct 383 ms 786700 KB Output is correct
12 Correct 366 ms 786852 KB Output is correct
13 Correct 356 ms 786948 KB Output is correct
14 Correct 347 ms 786792 KB Output is correct
15 Correct 411 ms 787004 KB Output is correct
16 Correct 984 ms 913928 KB Output is correct
17 Incorrect 1071 ms 930628 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 784940 KB Output is correct
2 Correct 335 ms 784700 KB Output is correct
3 Correct 361 ms 784712 KB Output is correct
4 Runtime error 672 ms 912784 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -