Submission #810246

#	Time	Username	Problem	Language	Result	Execution time	Memory
810246		vjudge1	Railway Trip 2 (JOI22_ho_t4)	C++17	27 / 100	2070 ms	136744 KiB

Main

#include <bits/stdc++.h>



using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 5e5 + 9 , mod = 1e9 + 7;
ll  d[N] = {} , a[N] = {}, dp[N] ,  b[N] , c[N];

struct edge{
ll a , b, c;
};

vector<pair<int,int>>v[N] , v1 , v2;
vector<edge>vc;
multiset<ll>st[N][2] , st1[N][2];
void solve(){
    ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
    cin>>n>>k;
    cin>>m;
    for(i = 1; i <= n; i++)
        a[i] = b[i] = i;
    for(i = 1; i <= m; i++){
        cin>>l>>r;
        if(l > r){
            x = max(l - k + 1 , r + 1);
           // for(j = l ; j >= x; j--)
           //     a[j] = min(a[j] , r);
            st[l][0].insert(r);
            st[x][1].insert(r);
        }else {
            x = min(l + k - 1 , r - 1);
            st1[l][0].insert(r);
            st1[x][1].insert(r);
            //for(j = l; j <= x; j++)
            //    b[j] = max(b[j] , r);
            vc.pb({l , x , r});
        }
    }
    multiset<ll>v;
    for(i = n;  i >= 1; i--){
        for(auto it : st[i][0])
            v.insert(it);
        if(v.size())
        a[i] = min(a[i] , *v.begin());
        for(auto it : st[i][1])
            v.erase(v.find(it));
    }
    v.clear();
    for(i = 1;  i <= n; i++){
        for(auto it : st1[i][0])
            v.insert(it);
        if(v.size())
            b[i] = max(b[i] , *v.rbegin());
        for(auto it : st1[i][1])
            v.erase(v.find(it));
    }
    set<ll>st;
    cin>>q;
    while(q--){
        cin>>x>>y;
        set<ll>st;
        for(i = 1; i <= n; i++){
            d[i] = 1e9;
            st.insert(i);
        }
        queue<int>qq;
        qq.push(x);
        st.erase(x);
        d[x] = 0;
        while(!qq.empty()){
            i=  qq.front();
            qq.pop();
            auto it = st.lower_bound(i);
            while(st.size() && it != st.end() && *it <= b[i]){
                d[*it] = d[i] + 1;
                qq.push(*it);
                st.erase(it);
                it = st.lower_bound(i);
            }
            while(st.size() && *st.begin() < i){
                auto it = st.lower_bound(i);
                it--;
                if(*it < a[i])
                    break;
                d[*it] = d[i] + 1;
                qq.push(*it);
                st.erase(it);
            }
        }
        if(d[y] == 1e9)
            d[y] = -1;
        cout<<d[y]<<"\n";
    }

}

int main(){

     TL;
  /*   #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
     #endif
     */
int t = 1;
//cin>>t;

while(t--)
     {
     solve();
     }

}
// Author : حسن

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:36:16: warning: unused variable 'j' [-Wunused-variable]
   36 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                ^
Main.cpp:36:26: warning: unused variable 'z' [-Wunused-variable]
   36 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                          ^
Main.cpp:36:29: warning: unused variable 's' [-Wunused-variable]
   36 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                             ^
Main.cpp:36:37: warning: unused variable 'f' [-Wunused-variable]
   36 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
Main.cpp:36:61: warning: unused variable 'mn' [-Wunused-variable]
   36 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                             ^~
Main.cpp:36:74: warning: unused variable 'mx' [-Wunused-variable]
   36 |     ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                                          ^~

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