Submission #1085900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085900		Bananabread	Passport (JOI23_passport)	C++17	48 / 100	820 ms	455688 KiB

passport

#include<bits/stdc++.h>
#define ll long long
#define ntr "\n"
#define mod (ll)(1e9+7)
#define taskname "temp"
#define frep freopen(taskname".inp","r",stdin); freopen(taskname".out","w",stdout);
using namespace std;
vector<array<int,3>> adj[2501][2501];
ll dist[2501][2501];
ll vis[2501][2501];
ll n,q;
ll l[200001];
ll r[200001];
void sub1(){
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    ll mx=r[1];
    ll ans=1;
    priority_queue<ll> q;
    for(int i=1;i<=n;i++){
        if(i>mx){
            cout<<-1;
            return;
        }
        q.push(r[i]);
        if(i==mx){
            ans++;
            mx=q.top();
        }
    }
    cout<<ans;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //frep;
    cin>>n;
    if(n>2500){
        sub1();
        return 0;
    }
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }
    for(int i=1;i<=n;i++){
        ll mx=0,mn=1e18;
        adj[l[i]][r[i]].push_back({i,i,1});
        for(int j=i;j<=n;j++){
            mx=max(mx,r[j]);
            mn=min(mn,l[j]);
            if(i!=j){
                adj[i][mx].push_back({i,j,1});
                adj[mn][j].push_back({i,j,1});
                adj[i+1][j].push_back({i,j,0});
                adj[i][j-1].push_back({i,j,0});
            }
        }
    }
    memset(dist,0x3f,sizeof(dist));
    dist[1][n]=0;
    deque<array<ll,2>> dq;
    dq.push_front({1,n});
    while(!dq.empty()){
        ll u=dq.front()[0],v=dq.front()[1];
        dq.pop_front();
        if(vis[u][v]) continue;
        vis[u][v]=1;
        for(auto i:adj[u][v]){
            ll x=i[0],y=i[1],w=i[2];
            if(dist[x][y]>dist[u][v]+w){
                dist[x][y]=dist[u][v]+w;
                if(w==0){
                    dq.push_front({x,y});
                }
                else{
                    dq.push_back({x,y});
                }
            }
        }
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        ll x;
        cin>>x;
        cout<<(dist[x][x] >= 1e18 ? -1 : dist[x][x])<<ntr;
    }
}

• Subtask 1: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 0 / 46