oj.uz

Submission #730877

# Submission time Handle Problem Language Result Execution time Memory
730877 2023-04-26T14:48:28 Z grogu Passport (JOI23_passport) C++14
16 / 100
 1209 ms 1027440 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<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 412 ms 784688 KB Output is correct
2 Correct 356 ms 784704 KB Output is correct
3 Correct 358 ms 784604 KB Output is correct
4 Runtime error 546 ms 897772 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 362 ms 784652 KB Output is correct
2 Correct 372 ms 784728 KB Output is correct
3 Correct 370 ms 784740 KB Output is correct
4 Correct 376 ms 784656 KB Output is correct
5 Correct 351 ms 784776 KB Output is correct
6 Correct 357 ms 784604 KB Output is correct
7 Correct 407 ms 784684 KB Output is correct
8 Correct 382 ms 784648 KB Output is correct
9 Correct 352 ms 784732 KB Output is correct
10 Correct 365 ms 784732 KB Output is correct
11 Correct 358 ms 787980 KB Output is correct
12 Correct 364 ms 788172 KB Output is correct
13 Correct 387 ms 788300 KB Output is correct
14 Correct 377 ms 788044 KB Output is correct
15 Correct 356 ms 788384 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 784652 KB Output is correct
2 Correct 372 ms 784728 KB Output is correct
3 Correct 370 ms 784740 KB Output is correct
4 Correct 376 ms 784656 KB Output is correct
5 Correct 351 ms 784776 KB Output is correct
6 Correct 357 ms 784604 KB Output is correct
7 Correct 407 ms 784684 KB Output is correct
8 Correct 382 ms 784648 KB Output is correct
9 Correct 352 ms 784732 KB Output is correct
10 Correct 365 ms 784732 KB Output is correct
11 Correct 358 ms 787980 KB Output is correct
12 Correct 364 ms 788172 KB Output is correct
13 Correct 387 ms 788300 KB Output is correct
14 Correct 377 ms 788044 KB Output is correct
15 Correct 356 ms 788384 KB Output is correct
16 Correct 1139 ms 999244 KB Output is correct
17 Incorrect 1209 ms 1027440 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 784652 KB Output is correct
2 Correct 372 ms 784728 KB Output is correct
3 Correct 370 ms 784740 KB Output is correct
4 Correct 376 ms 784656 KB Output is correct
5 Correct 351 ms 784776 KB Output is correct
6 Correct 357 ms 784604 KB Output is correct
7 Correct 407 ms 784684 KB Output is correct
8 Correct 382 ms 784648 KB Output is correct
9 Correct 352 ms 784732 KB Output is correct
10 Correct 365 ms 784732 KB Output is correct
11 Correct 358 ms 787980 KB Output is correct
12 Correct 364 ms 788172 KB Output is correct
13 Correct 387 ms 788300 KB Output is correct
14 Correct 377 ms 788044 KB Output is correct
15 Correct 356 ms 788384 KB Output is correct
16 Correct 1139 ms 999244 KB Output is correct
17 Incorrect 1209 ms 1027440 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 784688 KB Output is correct
2 Correct 356 ms 784704 KB Output is correct
3 Correct 358 ms 784604 KB Output is correct
4 Runtime error 546 ms 897772 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -