oj.uz

Submission #730866

# Submission time Handle Problem Language Result Execution time Memory
730866 2023-04-26T14:36:52 Z grogu Passport (JOI23_passport) C++14
0 / 100
 24 ms 49536 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];
ll dis[maxn*maxn];
ll lg2[maxn];
pll st[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});
            }
        }
    }
}
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;
}
pll 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);
    return ans;
}
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};
    }
    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))]);
        }
    }
    for(ll len = 1;len<=n;len++){
        for(ll i = 1;i+len-1<=n;i++){
            ll l = i,r = i+len-1;
            pll p = get(l,r);
            if(p.fi==p.sc){
                upd(kod({l,r}),kod(a[p.fi]),1);
            }else{
                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 21 ms 49460 KB Output is correct
2 Correct 20 ms 49524 KB Output is correct
3 Correct 22 ms 49448 KB Output is correct
4 Runtime error 2 ms 756 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49492 KB Output is correct
2 Correct 19 ms 49472 KB Output is correct
3 Correct 22 ms 49492 KB Output is correct
4 Correct 20 ms 49460 KB Output is correct
5 Correct 21 ms 49508 KB Output is correct
6 Correct 24 ms 49516 KB Output is correct
7 Correct 23 ms 49492 KB Output is correct
8 Correct 24 ms 49492 KB Output is correct
9 Correct 21 ms 49456 KB Output is correct
10 Correct 21 ms 49536 KB Output is correct
11 Runtime error 2 ms 724 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49492 KB Output is correct
2 Correct 19 ms 49472 KB Output is correct
3 Correct 22 ms 49492 KB Output is correct
4 Correct 20 ms 49460 KB Output is correct
5 Correct 21 ms 49508 KB Output is correct
6 Correct 24 ms 49516 KB Output is correct
7 Correct 23 ms 49492 KB Output is correct
8 Correct 24 ms 49492 KB Output is correct
9 Correct 21 ms 49456 KB Output is correct
10 Correct 21 ms 49536 KB Output is correct
11 Runtime error 2 ms 724 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49492 KB Output is correct
2 Correct 19 ms 49472 KB Output is correct
3 Correct 22 ms 49492 KB Output is correct
4 Correct 20 ms 49460 KB Output is correct
5 Correct 21 ms 49508 KB Output is correct
6 Correct 24 ms 49516 KB Output is correct
7 Correct 23 ms 49492 KB Output is correct
8 Correct 24 ms 49492 KB Output is correct
9 Correct 21 ms 49456 KB Output is correct
10 Correct 21 ms 49536 KB Output is correct
11 Runtime error 2 ms 724 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49460 KB Output is correct
2 Correct 20 ms 49524 KB Output is correct
3 Correct 22 ms 49448 KB Output is correct
4 Runtime error 2 ms 756 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -