Submission #1287178

#TimeUsernameProblemLanguageResultExecution timeMemory
1287178denislavPassport (JOI23_passport)C++20
40 / 100
2094 ms14568 KiB
# include <iostream>
using namespace std;

const int MAX=3e3+11;

int n,q;
pair<int,int> a[MAX];

int dp[MAX][MAX];

int rec(int l, int r)
{
    if(l==1 and r==n) return 0;
    if(dp[l][r]!=0) return dp[l][r];

    int ans=1e9;
    for(int i=l;i<=r;i++)
    {
        int l2=min(a[i].first,l);
        int r2=max(a[i].second,r);
        if(!(l2==l and r2==r)) ans=min(ans,rec(l2,r2)+1);
    }

    dp[l][r]=ans;
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;

    cin>>q;
    while(q--)
    {
        int pos;
        cin>>pos;
        int ans=rec(a[pos].first,a[pos].second);
        if(ans==1e9) cout<<-1<<"\n";
        else cout<<ans+1<<"\n";
    }

    return 0;
}



#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...