oj.uz

Submission #730884

# Submission time Handle Problem Language Result Execution time Memory
730884 2023-04-26T14:59:31 Z grogu Passport (JOI23_passport) C++14
16 / 100
 2000 ms 930620 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 maxx 200005
#define lg 15
ll n,q;
pll a[maxx];
vector<ll> 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);
    //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;
    queue<ll> pq;
    pq.push(poc);
    while(pq.size()){
        ll u = pq.front();
        pq.pop();
        for(ll s : g[u]){
            if(dis[u]+1<dis[s]){
                dis[s] = dis[u] + 1;
                pq.push(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++) if((1<<j)<maxn) 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;
    }
    if(n>2500){
        cin >> q;
        cin >> q;
        ll i = 1;
        ll ans = 0;
        ll r = a[i].sc;
        while(i!=n){
            ans++;
            for(ll j = i;j<=r;j++) i = max(i,a[j].sc);
        }
        cout<<ans<<endl;
        return 0;
    }
    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

5
1 1
2 3
1 5
3 4
5 5
5
1
2
3
4
5

4
1 2
1 2
3 4
3 4
4
1
2
3
4
**/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 784724 KB Output is correct
2 Correct 349 ms 784836 KB Output is correct
3 Correct 348 ms 784748 KB Output is correct
4 Execution timed out 2081 ms 595404 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 784708 KB Output is correct
2 Correct 352 ms 784720 KB Output is correct
3 Correct 349 ms 784804 KB Output is correct
4 Correct 355 ms 784588 KB Output is correct
5 Correct 341 ms 784764 KB Output is correct
6 Correct 345 ms 784720 KB Output is correct
7 Correct 340 ms 784716 KB Output is correct
8 Correct 377 ms 784664 KB Output is correct
9 Correct 343 ms 784680 KB Output is correct
10 Correct 351 ms 784712 KB Output is correct
11 Correct 350 ms 786788 KB Output is correct
12 Correct 360 ms 787044 KB Output is correct
13 Correct 367 ms 786948 KB Output is correct
14 Correct 365 ms 786764 KB Output is correct
15 Correct 368 ms 786892 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 784708 KB Output is correct
2 Correct 352 ms 784720 KB Output is correct
3 Correct 349 ms 784804 KB Output is correct
4 Correct 355 ms 784588 KB Output is correct
5 Correct 341 ms 784764 KB Output is correct
6 Correct 345 ms 784720 KB Output is correct
7 Correct 340 ms 784716 KB Output is correct
8 Correct 377 ms 784664 KB Output is correct
9 Correct 343 ms 784680 KB Output is correct
10 Correct 351 ms 784712 KB Output is correct
11 Correct 350 ms 786788 KB Output is correct
12 Correct 360 ms 787044 KB Output is correct
13 Correct 367 ms 786948 KB Output is correct
14 Correct 365 ms 786764 KB Output is correct
15 Correct 368 ms 786892 KB Output is correct
16 Correct 919 ms 913692 KB Output is correct
17 Incorrect 1018 ms 930620 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 784708 KB Output is correct
2 Correct 352 ms 784720 KB Output is correct
3 Correct 349 ms 784804 KB Output is correct
4 Correct 355 ms 784588 KB Output is correct
5 Correct 341 ms 784764 KB Output is correct
6 Correct 345 ms 784720 KB Output is correct
7 Correct 340 ms 784716 KB Output is correct
8 Correct 377 ms 784664 KB Output is correct
9 Correct 343 ms 784680 KB Output is correct
10 Correct 351 ms 784712 KB Output is correct
11 Correct 350 ms 786788 KB Output is correct
12 Correct 360 ms 787044 KB Output is correct
13 Correct 367 ms 786948 KB Output is correct
14 Correct 365 ms 786764 KB Output is correct
15 Correct 368 ms 786892 KB Output is correct
16 Correct 919 ms 913692 KB Output is correct
17 Incorrect 1018 ms 930620 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 784724 KB Output is correct
2 Correct 349 ms 784836 KB Output is correct
3 Correct 348 ms 784748 KB Output is correct
4 Execution timed out 2081 ms 595404 KB Time limit exceeded
5 Halted 0 ms 0 KB -