oj.uz

Submission #730874

# Submission time Handle Problem Language Result Execution time Memory
730874 2023-04-26T14:46:16 Z grogu Passport (JOI23_passport) C++14
16 / 100
 989 ms 439512 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 2505
#define lg 12
ll n,q;
pll a[maxn];
vector<pll> 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,w});
    //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;
    priority_queue<pll> pq;
    pq.push({0,poc});
    while(pq.size()){
        pll p = pq.top();
        ll u = p.sc;
        ll cur = -p.fi;
        pq.pop();
        if(cur!=dis[u]) continue;
        for(pll p : g[u]){
            ll s = p.fi;
            ll w = p.sc;
            if(cur+w<dis[s]){
                dis[s] = cur+w;
                pq.push({-dis[s],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 95 ms 196716 KB Output is correct
2 Correct 95 ms 196784 KB Output is correct
3 Correct 88 ms 196792 KB Output is correct
4 Runtime error 179 ms 299464 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 87 ms 196764 KB Output is correct
2 Correct 94 ms 196812 KB Output is correct
3 Correct 94 ms 196760 KB Output is correct
4 Correct 100 ms 196804 KB Output is correct
5 Correct 93 ms 196816 KB Output is correct
6 Correct 88 ms 196716 KB Output is correct
7 Correct 91 ms 196784 KB Output is correct
8 Correct 95 ms 196812 KB Output is correct
9 Correct 90 ms 196840 KB Output is correct
10 Correct 89 ms 196844 KB Output is correct
11 Correct 107 ms 200112 KB Output is correct
12 Correct 105 ms 200372 KB Output is correct
13 Correct 103 ms 200392 KB Output is correct
14 Correct 100 ms 200124 KB Output is correct
15 Correct 99 ms 200472 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 196764 KB Output is correct
2 Correct 94 ms 196812 KB Output is correct
3 Correct 94 ms 196760 KB Output is correct
4 Correct 100 ms 196804 KB Output is correct
5 Correct 93 ms 196816 KB Output is correct
6 Correct 88 ms 196716 KB Output is correct
7 Correct 91 ms 196784 KB Output is correct
8 Correct 95 ms 196812 KB Output is correct
9 Correct 90 ms 196840 KB Output is correct
10 Correct 89 ms 196844 KB Output is correct
11 Correct 107 ms 200112 KB Output is correct
12 Correct 105 ms 200372 KB Output is correct
13 Correct 103 ms 200392 KB Output is correct
14 Correct 100 ms 200124 KB Output is correct
15 Correct 99 ms 200472 KB Output is correct
16 Correct 874 ms 411336 KB Output is correct
17 Incorrect 989 ms 439512 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 196764 KB Output is correct
2 Correct 94 ms 196812 KB Output is correct
3 Correct 94 ms 196760 KB Output is correct
4 Correct 100 ms 196804 KB Output is correct
5 Correct 93 ms 196816 KB Output is correct
6 Correct 88 ms 196716 KB Output is correct
7 Correct 91 ms 196784 KB Output is correct
8 Correct 95 ms 196812 KB Output is correct
9 Correct 90 ms 196840 KB Output is correct
10 Correct 89 ms 196844 KB Output is correct
11 Correct 107 ms 200112 KB Output is correct
12 Correct 105 ms 200372 KB Output is correct
13 Correct 103 ms 200392 KB Output is correct
14 Correct 100 ms 200124 KB Output is correct
15 Correct 99 ms 200472 KB Output is correct
16 Correct 874 ms 411336 KB Output is correct
17 Incorrect 989 ms 439512 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 196716 KB Output is correct
2 Correct 95 ms 196784 KB Output is correct
3 Correct 88 ms 196792 KB Output is correct
4 Runtime error 179 ms 299464 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -