oj.uz

Submission #730867

# Submission time Handle Problem Language Result Execution time Memory
730867 2023-04-26T14:37:16 Z grogu Passport (JOI23_passport) C++14
0 / 100
 907 ms 299360 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 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 116 ms 196812 KB Output is correct
2 Correct 87 ms 196684 KB Output is correct
3 Correct 88 ms 196760 KB Output is correct
4 Runtime error 181 ms 299360 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 97 ms 196784 KB Output is correct
2 Correct 99 ms 196720 KB Output is correct
3 Correct 87 ms 196808 KB Output is correct
4 Correct 90 ms 196728 KB Output is correct
5 Correct 91 ms 196788 KB Output is correct
6 Correct 89 ms 196724 KB Output is correct
7 Correct 88 ms 196816 KB Output is correct
8 Correct 90 ms 196756 KB Output is correct
9 Correct 95 ms 196764 KB Output is correct
10 Correct 89 ms 196812 KB Output is correct
11 Correct 765 ms 199588 KB Output is correct
12 Correct 907 ms 200172 KB Output is correct
13 Correct 797 ms 199972 KB Output is correct
14 Incorrect 830 ms 199892 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 196784 KB Output is correct
2 Correct 99 ms 196720 KB Output is correct
3 Correct 87 ms 196808 KB Output is correct
4 Correct 90 ms 196728 KB Output is correct
5 Correct 91 ms 196788 KB Output is correct
6 Correct 89 ms 196724 KB Output is correct
7 Correct 88 ms 196816 KB Output is correct
8 Correct 90 ms 196756 KB Output is correct
9 Correct 95 ms 196764 KB Output is correct
10 Correct 89 ms 196812 KB Output is correct
11 Correct 765 ms 199588 KB Output is correct
12 Correct 907 ms 200172 KB Output is correct
13 Correct 797 ms 199972 KB Output is correct
14 Incorrect 830 ms 199892 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 196784 KB Output is correct
2 Correct 99 ms 196720 KB Output is correct
3 Correct 87 ms 196808 KB Output is correct
4 Correct 90 ms 196728 KB Output is correct
5 Correct 91 ms 196788 KB Output is correct
6 Correct 89 ms 196724 KB Output is correct
7 Correct 88 ms 196816 KB Output is correct
8 Correct 90 ms 196756 KB Output is correct
9 Correct 95 ms 196764 KB Output is correct
10 Correct 89 ms 196812 KB Output is correct
11 Correct 765 ms 199588 KB Output is correct
12 Correct 907 ms 200172 KB Output is correct
13 Correct 797 ms 199972 KB Output is correct
14 Incorrect 830 ms 199892 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 196812 KB Output is correct
2 Correct 87 ms 196684 KB Output is correct
3 Correct 88 ms 196760 KB Output is correct
4 Runtime error 181 ms 299360 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -