Submission #1235986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235986		hamanp87	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	293 ms	227248 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

//#pragma GCC optimize("03,unroll-loops")
//#pragma GCC target("avx2")
//#pragma GCC target("sse4")

#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
//#define randi uniform_int_distribution<long long>
#define damoon(v) v.resize(unique(all(v))-v.begin())
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//randi dist(0,10000000000000000);

typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,bool> pib;
typedef pair<long long,bool> plb;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef vector<int> veci;
typedef vector<long long> vecl;
typedef vector<bool> vecb;
typedef vector<pii> vecp;
typedef set<int> seti;
typedef set<long long> setl;
typedef set<pii> setp;
typedef map<int,int> mapii;
typedef map<long long,long long> mapll;
typedef map<int,bool> mapib;
typedef map<long long,bool> maplb;

const int inf=1e9,mod=1e9+7,neginf=-1e9,N=1e5+5,LG=17;
const double PI=acos(-1);
int n,K,m,lg2[N],spmn[LG][LG][N],spmx[LG][LG][N];

void initialize(int k)
{
    for(int j=1;j<LG;j++)
    {
        int tmp=1<<j;
        for(int i=1;i+tmp-1<=n;i++)
        {
            spmn[k][j][i]=min(spmn[k][j-1][i],spmn[k][j-1][i+(tmp>>1)]);
            spmx[k][j][i]=max(spmx[k][j-1][i],spmx[k][j-1][i+(tmp>>1)]);
        }
    }
}

inline int RMQn(int k,int l,int r)
{
    int j=lg2[r-l+1];
    return min(spmn[k][j][l],spmn[k][j][r-(1<<j)+1]);
}

inline int RMQx(int k,int l,int r)
{
    int j=lg2[r-l+1];
    return max(spmx[k][j][l],spmx[k][j][r-(1<<j)+1]);
}

void solve()
{
    cin>>n>>K>>m;
    lg2[1]=0;
    for(int i=2;i<N;i++)
        lg2[i]=lg2[i>>1]+1;

    vector<veci> fow(N),baw(N);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a<b)
        {
            fow[a].pub(b);
            fow[min(a+K,b)].pub(-b);
        }
        else
        {
            baw[a].pub(b);
            baw[max(a-K,b)].pub(-b);
        }
    }

    {
        multiset<int> ss;
        for(int i=1;i<=n;i++)
        {
            for(int x:fow[i])
            {
                if(x>0)
                    ss.insert(x);
                else
                    ss.erase(ss.find(-x));
            }
            if(ss.empty())
            {
                spmn[0][0][i]=spmx[0][0][i]=i;
            }
            else
            {
                spmn[0][0][i]=i;
                spmx[0][0][i]=*ss.rbegin();
            }
        }
    }

    {
        multiset<int> ss;
        for(int i=n;i>=1;i--)
        {
            for(int x:baw[i])
            {
                if(x>0)
                    ss.insert(x);
                else
                    ss.erase(ss.find(-x));
            }
            if(ss.size())
            {
                spmn[0][0][i]=min(spmn[0][0][i],*ss.begin());
                spmx[0][0][i]=max(spmx[0][0][i],i);
            }
        }
    }

    initialize(0);

    for(int k=1;k<LG;k++)
    {
        for(int i=1;i<=n;i++)
        {
            int l1=RMQn(k-1,i,i);
            int r1=RMQx(k-1,i,i);
            int l2=RMQn(k-1,l1,r1);
            int r2=RMQx(k-1,l1,r1);

            spmn[k][0][i]=l2;
            spmx[k][0][i]=r2;
        }
        initialize(k);
    }

    int q;
    cin>>q;
    while(q--)
    {
        int a,b;
        cin>>a>>b;

        if(a==b)
        {
            cout<<"0\n";
            continue;
        }

        int ans=0,cl=a,cr=a;

        for(int k=LG-1;k>=0;k--)
        {
            int nl=RMQn(k,cl,cr);
            int nr=RMQx(k,cl,cr);

            if(b<nl or b>nr)
            {
                ans+=(1<<k);
                cl=nl;
                cr=nr;
            }
        }

        int nl=RMQn(0,cl,cr);
        int nr=RMQx(0,cl,cr);

        if(b>=nl and b<=nr)
            cout<<ans+1<<"\n";
        else
            cout<<"-1\n";
    }
}

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

    //ifstream fin("in.txt");
    //ofstream fout("out.txt");

    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13