oj.uz

Submission #730870

# Submission time Handle Problem Language Result Execution time Memory
730870 2023-04-26T14:41:59 Z grogu Passport (JOI23_passport) C++14
16 / 100
 1016 ms 439580 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) ans.fi = min(p.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) ans.sc = min(p.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 91 ms 196784 KB Output is correct
2 Correct 88 ms 196776 KB Output is correct
3 Correct 88 ms 196736 KB Output is correct
4 Runtime error 180 ms 299440 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 93 ms 196796 KB Output is correct
2 Correct 95 ms 196800 KB Output is correct
3 Correct 91 ms 196760 KB Output is correct
4 Correct 100 ms 196804 KB Output is correct
5 Correct 116 ms 196824 KB Output is correct
6 Correct 93 ms 197008 KB Output is correct
7 Correct 88 ms 196772 KB Output is correct
8 Correct 89 ms 196768 KB Output is correct
9 Correct 90 ms 196860 KB Output is correct
10 Correct 94 ms 196824 KB Output is correct
11 Correct 98 ms 200240 KB Output is correct
12 Correct 98 ms 200308 KB Output is correct
13 Correct 97 ms 200356 KB Output is correct
14 Correct 111 ms 200132 KB Output is correct
15 Correct 101 ms 200460 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 196796 KB Output is correct
2 Correct 95 ms 196800 KB Output is correct
3 Correct 91 ms 196760 KB Output is correct
4 Correct 100 ms 196804 KB Output is correct
5 Correct 116 ms 196824 KB Output is correct
6 Correct 93 ms 197008 KB Output is correct
7 Correct 88 ms 196772 KB Output is correct
8 Correct 89 ms 196768 KB Output is correct
9 Correct 90 ms 196860 KB Output is correct
10 Correct 94 ms 196824 KB Output is correct
11 Correct 98 ms 200240 KB Output is correct
12 Correct 98 ms 200308 KB Output is correct
13 Correct 97 ms 200356 KB Output is correct
14 Correct 111 ms 200132 KB Output is correct
15 Correct 101 ms 200460 KB Output is correct
16 Correct 813 ms 411388 KB Output is correct
17 Incorrect 1016 ms 439580 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 196796 KB Output is correct
2 Correct 95 ms 196800 KB Output is correct
3 Correct 91 ms 196760 KB Output is correct
4 Correct 100 ms 196804 KB Output is correct
5 Correct 116 ms 196824 KB Output is correct
6 Correct 93 ms 197008 KB Output is correct
7 Correct 88 ms 196772 KB Output is correct
8 Correct 89 ms 196768 KB Output is correct
9 Correct 90 ms 196860 KB Output is correct
10 Correct 94 ms 196824 KB Output is correct
11 Correct 98 ms 200240 KB Output is correct
12 Correct 98 ms 200308 KB Output is correct
13 Correct 97 ms 200356 KB Output is correct
14 Correct 111 ms 200132 KB Output is correct
15 Correct 101 ms 200460 KB Output is correct
16 Correct 813 ms 411388 KB Output is correct
17 Incorrect 1016 ms 439580 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 196784 KB Output is correct
2 Correct 88 ms 196776 KB Output is correct
3 Correct 88 ms 196736 KB Output is correct
4 Runtime error 180 ms 299440 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -