oj.uz

Submission #730876

# Submission time Handle Problem Language Result Execution time Memory
730876 2023-04-26T14:48:05 Z grogu Passport (JOI23_passport) C++14
16 / 100
 963 ms 439492 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 13
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 196808 KB Output is correct
2 Correct 89 ms 196720 KB Output is correct
3 Correct 106 ms 196816 KB Output is correct
4 Runtime error 189 ms 299596 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 88 ms 196784 KB Output is correct
2 Correct 93 ms 196832 KB Output is correct
3 Correct 101 ms 196820 KB Output is correct
4 Correct 95 ms 196764 KB Output is correct
5 Correct 89 ms 196792 KB Output is correct
6 Correct 89 ms 196780 KB Output is correct
7 Correct 99 ms 196812 KB Output is correct
8 Correct 97 ms 196804 KB Output is correct
9 Correct 96 ms 196760 KB Output is correct
10 Correct 89 ms 196724 KB Output is correct
11 Correct 98 ms 200016 KB Output is correct
12 Correct 104 ms 200340 KB Output is correct
13 Correct 107 ms 200464 KB Output is correct
14 Correct 102 ms 200140 KB Output is correct
15 Correct 102 ms 200460 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 196784 KB Output is correct
2 Correct 93 ms 196832 KB Output is correct
3 Correct 101 ms 196820 KB Output is correct
4 Correct 95 ms 196764 KB Output is correct
5 Correct 89 ms 196792 KB Output is correct
6 Correct 89 ms 196780 KB Output is correct
7 Correct 99 ms 196812 KB Output is correct
8 Correct 97 ms 196804 KB Output is correct
9 Correct 96 ms 196760 KB Output is correct
10 Correct 89 ms 196724 KB Output is correct
11 Correct 98 ms 200016 KB Output is correct
12 Correct 104 ms 200340 KB Output is correct
13 Correct 107 ms 200464 KB Output is correct
14 Correct 102 ms 200140 KB Output is correct
15 Correct 102 ms 200460 KB Output is correct
16 Correct 859 ms 411444 KB Output is correct
17 Incorrect 963 ms 439492 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 196784 KB Output is correct
2 Correct 93 ms 196832 KB Output is correct
3 Correct 101 ms 196820 KB Output is correct
4 Correct 95 ms 196764 KB Output is correct
5 Correct 89 ms 196792 KB Output is correct
6 Correct 89 ms 196780 KB Output is correct
7 Correct 99 ms 196812 KB Output is correct
8 Correct 97 ms 196804 KB Output is correct
9 Correct 96 ms 196760 KB Output is correct
10 Correct 89 ms 196724 KB Output is correct
11 Correct 98 ms 200016 KB Output is correct
12 Correct 104 ms 200340 KB Output is correct
13 Correct 107 ms 200464 KB Output is correct
14 Correct 102 ms 200140 KB Output is correct
15 Correct 102 ms 200460 KB Output is correct
16 Correct 859 ms 411444 KB Output is correct
17 Incorrect 963 ms 439492 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 196808 KB Output is correct
2 Correct 89 ms 196720 KB Output is correct
3 Correct 106 ms 196816 KB Output is correct
4 Runtime error 189 ms 299596 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -