Submission #1070693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070693		epicci23	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	1159 ms	182680 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 1e5 + 5;
const int LOG = 20;
const int INF = 1e18;

struct SegT{
  int n;
  vector<int> mn,mx;
  SegT(int _n){
  	this->n=_n;
  	mn.assign(4*_n+5,INF);
  	mx.assign(4*_n+5,-INF);
  }
  void upd(int rt,int l,int r,int ind,int u,int u2){
    if(r<ind || l>ind) return;
    if(l==r){
      mn[rt]=u;
      mx[rt]=u2;
      return;
    }
    int m=(l+r)/2;
    upd(rt*2,l,m,ind,u,u2),upd(rt*2+1,m+1,r,ind,u,u2);
    mn[rt]=min(mn[rt*2],mn[rt*2+1]);
    mx[rt]=max(mx[rt*2],mx[rt*2+1]);
  }
  void upd(int ind,int u,int u2){
  	upd(1,1,n,ind,u,u2);
  }
  int max_query(int rt,int l,int r,int gl,int gr){
  	if(r<gl || l>gr) return -INF;
  	if(l>=gl && r<=gr) return mx[rt];
  	int m=(l+r)/2;
  	return max(max_query(rt*2,l,m,gl,gr),max_query(rt*2+1,m+1,r,gl,gr));
  }
  int min_query(int rt,int l,int r,int gl,int gr){
  	if(r<gl || l>gr) return INF;
  	if(l>=gl && r<=gr) return mn[rt];
  	int m=(l+r)/2;
  	return min(min_query(rt*2,l,m,gl,gr),min_query(rt*2+1,m+1,r,gl,gr));
  }
  int max_query(int l,int r){
  	return max_query(1,1,n,l,r);
  }
  int min_query(int l,int r){
  	return min_query(1,1,n,l,r);
  }
};

void _(){
  int n,k,m;
  cin >> n >> k >> m;
  int lift[N][LOG][2];
  vector<array<int,2>> v[n+5];
  multiset<int> ms[2];
  for(int i=0;i<m;i++){
  	int a,b;
  	cin >> a >> b;
    if(a>b){
      v[max(a-k+1,b+1)].push_back({b,1});
      v[a+1].push_back({b,0}); 
    }
    else{
    	v[a].push_back({b,1});
    	v[min(a+k-1,b-1)+1].push_back({b,0});
    }
  }
  for(int i=1;i<=n;i++){
  	for(array<int,2> x:v[i]){
  	  if(x[0]>=i){
        if(x[1]==0) ms[0].erase(ms[0].find(x[0]));
        else ms[0].insert(x[0]);
  	  }
  	  else{
  	  	if(x[1]==0) ms[1].erase(ms[1].find(x[0]));
        else ms[1].insert(x[0]);
  	  }
  	}
  	if(ms[0].empty()) lift[i][0][0]=i;
  	else lift[i][0][0]=*ms[0].rbegin();
  	if(ms[1].empty()) lift[i][0][1]=i;
  	else lift[i][0][1]=*ms[1].begin();
  }
  vector<SegT> seg(LOG,SegT(n));
  for(int i=1;i<=n;i++) seg[0].upd(i,lift[i][0][1],lift[i][0][0]);
  
  for(int j=1;j<LOG;j++){
  	for(int i=1;i<=n;i++){
  	  lift[i][j][0]=seg[j-1].max_query(lift[i][j-1][1],lift[i][j-1][0]);
  	  lift[i][j][1]=seg[j-1].min_query(lift[i][j-1][1],lift[i][j-1][0]);
  	}
  	for(int i=1;i<=n;i++) seg[j].upd(i,lift[i][j][1],lift[i][j][0]);
  }
  int q;cin >> q;
  while(q--){
  	int a,b;
  	cin >> a >> b;
  	array<int,2> Expand={a,a};
  	bool ok=0;
  	int ans=1;
  	for(int j=LOG-1;j>=0;j--){
      int l=seg[j].min_query(Expand[0],Expand[1]);
      int r=seg[j].max_query(Expand[0],Expand[1]);
      if(min(l,Expand[0])<=b && b<=max(r,Expand[1])){
      	ok=1;
      	continue;
      }
      Expand[0]=min(l,Expand[0]);
      Expand[1]=max(r,Expand[1]);
      ans+=(1<<j);
  	}
  	if(!ok) cout << -1 << '\n';
  	else cout << ans << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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