Submission #1260900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260900		Szymon_Pilipczuk	Passport (JOI23_passport)	C++20	48 / 100	613 ms	25228 KiB

passport

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
int n;
int tr[5000];
pair<int,int> tr2[5000];
void add2(int p,int a,int b)
{
    p+= n;
    tr2[p] = {a,b};
    p/=2;
    while(p > 0)
    {
        tr2[p].st = min(tr2[p*2].st,tr2[p*2+1].st);
        tr2[p].nd = max(tr2[p*2].nd,tr2[p*2+1].nd);
        p/=2;
    }
}
pair<int,int> check2(int l,int r)
{
    pair<int,int> ans = {l,r};
    l+=n;
    r+=n;
    ans.st = min(ans.st,min(tr2[l].st,tr2[r].st));
    ans.nd = max(ans.nd,max(tr2[l].nd,tr2[r].nd));
    while(l/2 != r/2)
    {
        if(l%2==0)
        {
            ans.st = min(ans.st,tr2[l+1].st);
            ans.nd = max(ans.nd,tr2[l+1].nd);
        }
        if(r%2 == 1)
        {
            ans.st = min(ans.st,tr2[r-1].st);
            ans.nd = max(ans.nd,tr2[r-1].nd);
        }
        l/=2;r/=2;
    }
    return ans;
}
void add(int p,int v)
{
    p+=n;
    tr[p] = min(tr[p],v);
    p/=2;
    while(p > 0)
    {
        tr[p] = min(tr[p*2],tr[p*2+1]);
        p/=2;
    }
}
int check(int l,int r)
{   
    l += n;
    r += n;
    int ans = min(tr[l],tr[r]);
    while(l/2 != r/2)
    {
        if(l%2 == 0)ans = min(ans,tr[l+1]);
        if(r%2 == 1)ans = min(ans,tr[r-1]);
        l/=2;r/=2;
    }
    //cerr<<ans<<" "<<l<<" "<<r<<" "<<tr[l]<<"\n";
    return ans;
}
int ans[2500][2500];
map<pair<int,int>,vector<int>> prz;
int main()
{
    cin>>n;
    vector<pair<int,int>> b(n);
    rep(i,n*2)
    {
        tr[i] = inf;
    }
    rep(i,n)
    {
        cin>>b[i].st>>b[i].nd;
        b[i].st--;b[i].nd--;
        prz[b[i]].pb(i);
        add2(i,b[i].st,b[i].nd);
    }
    rep(i,n)
    {
        rep(j,n)
        {
            ans[i][j] = inf;
        }
    }
    rep(i,n)
    {
        for(int j = n-1;j>=i;j--)
        {
            if(i==0&&j==n-1) 
            {
                ans[i][j] = 0;
            }
            else
            {
                ans[i][j] = min(min(ans[check2(i,j).st][j],ans[i][check2(i,j).nd]),check(i,j))+1;
            }
            if(prz.contains({i,j}))
            {
                for(int q : prz[{i,j}])
                {
                    add(q,ans[i][j]);
                }
            }
            //cerr<<i<<" "<<j<<" "<<ans[i][j]<<" "<<ans[check2(i,j).st][j]<<" "<<ans[i][check2(i,j).nd]<<" "<<check(i,j)<<"\n";
            
        }
    }
    int q;
    cin>>q;
    rep(i,q)
    {
        int x;
        cin>>x;
        x--;
        if(ans[x][x] < inf)
        {
            cout<<ans[x][x]<<"\n";
        }
        else
        {
            cout<<-1<<"\n";
        }
    }
    



}

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