제출 #531717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531717		errorgorn	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	512 ms	70940 KiB

Main

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

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct ST{ //sparse table
	int arr[100005][18];
	
	ST(vector<int> v){
		rep(x,0,sz(v)) arr[x][0]=v[x];
		
		int layer=1;
		int curr=1;
		
		while (curr<100005){
			rep(x,0,100005-curr){
				arr[x][layer]=max(arr[x+curr][layer-1],arr[x][layer-1]);
			}
			
			layer++;
			curr<<=1;
		}
	}
	
	int query(int i,int j){
		int len=31-__builtin_clz(j-i+1);
		return max(arr[i][len],arr[j-(1<<len)+1][len]);
	}
};

struct ST2{ //sparse table
	int arr[100005][18];
	
	ST2(vector<int> v){
		rep(x,0,sz(v)) arr[x][0]=v[x];
		
		int layer=1;
		int curr=1;
		
		while (curr<100005){
			rep(x,0,100005-curr){
				arr[x][layer]=min(arr[x+curr][layer-1],arr[x][layer-1]);
			}
			
			layer++;
			curr<<=1;
		}
	}
	
	int query(int i,int j){
		int len=31-__builtin_clz(j-i+1);
		return min(arr[i][len],arr[j-(1<<len)+1][len]);
	}
};

int n,m,k,q;
vector<ii> fwd;
vector<ii> bwd;

#define iii pair<ii,int>
set<iii> s;

void ins(int l,int r,int v){
	auto it=--s.lb({{l+1,-1},-1});
	
	while (it!=s.end() && (*it).fi.fi<=r){
		iii temp=(*it);
		it++;
		
		s.erase(temp);
		if (temp.fi.fi<l) s.insert({{temp.fi.fi,l-1},temp.se});
		if (r<temp.fi.se) s.insert({{r+1,temp.fi.se},temp.se});
	}
	
	s.insert({{l,r},v});
}

ii tkd[100005][18]; //points to the guy that can go the furthest (l,r)

vector<int> vl,vr;
ii conv(int l,int r,int layer){
	int l2,r2;
	int temp1,temp2;
	
	tie(temp1,temp2)={
		tkd[l][layer].fi,
		tkd[r][layer].fi
	};
	if (vl[temp1]<vl[temp2]) l2=temp1;
	else l2=temp2;
	
	tie(temp1,temp2)={
		tkd[l][layer].se,
		tkd[r][layer].se
	};
	if (vr[temp1]>vr[temp2]) r2=temp1;
	else r2=temp2;
	
	return {l2,r2};
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k>>m;
	
	int a,b;
	rep(x,0,m){
		cin>>a>>b;
		
		if (a<b) fwd.pub({a,b});
		else bwd.pub({b,a});
	}
	
	s.clear();
	rep(x,0,n+1) s.insert(iii(ii(x,x),x));
	sort(all(fwd),[](ii i,ii j){
		return i.se<j.se;
	});
	for (auto it:fwd) ins(it.fi,min(it.se,it.fi+k-1),it.se);
	for (auto it:s) rep(x,it.fi.fi,it.fi.se+1) vr.pub(it.se);
	ST R=ST(vr);
	
	s.clear();
	rep(x,0,n+1) s.insert(iii(ii(x,x),x));
	sort(all(bwd),[](ii i,ii j){
		return i.fi>j.fi;
	});
	for (auto it:bwd) ins(max(it.fi,it.se-k+1),it.se,it.fi);
	for (auto it:s) rep(x,it.fi.fi,it.fi.se+1) vl.pub(it.se);
	ST2 L=ST2(vl);
	
	//rep(x,1,n+1) cout<<vl[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<vr[x]<<" "; cout<<endl;
	
	rep(x,1,n+1){ //furthest right guy
		int lo=vl[x]-1,hi=vr[x],mi;
		int val=R.query(vl[x],vr[x]);
		
		while (hi-lo>1){
			mi=hi+lo>>1;
			if (R.query(vl[x],mi)!=val) lo=mi;
			else hi=mi;
		}
		
		tkd[x][0].se=hi;
	}
	rep(x,1,n+1){ //furthest left guy
		int lo=vl[x],hi=vr[x]+1,mi;
		int val=L.query(vl[x],vr[x]);
		
		while (hi-lo>1){
			mi=hi+lo>>1;
			if (L.query(mi,vr[x])!=val) hi=mi;
			else lo=mi;
		}
		
		tkd[x][0].fi=lo;
	}
	
	//rep(x,1,n+1) cout<<vl[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<vr[x]<<" "; cout<<endl;
	//rep(x,1,n+1) cout<<tkd[x][0].fi<<" "<<tkd[x][0].se<<endl;
	
	rep(x,1,18){
		rep(y,1,n+1){
			tkd[y][x]=conv(tkd[y][x-1].fi,tkd[y][x-1].se,x-1);
		}
	}
	
	cin>>q;
	while (q--){
		cin>>a>>b;
		
		int l=a,r=a;
		int ans=1;
		rep(x,18,0){
			int l2,r2;
			tie(l2,r2)=conv(l,r,x);
			
			if (b<vl[l2] || vr[r2]<b){
				ans+=(1<<x);
				l=l2;
				r=r2;
			}
		}
		
		if (b<vl[l] || vr[r]<b){
			tie(l,r)=conv(l,r,0);
			ans++;
		}
		if (b<vl[l] || vr[r]<b) ans=-1;
		
		cout<<ans<<endl;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:160:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  160 |    mi=hi+lo>>1;
      |       ~~^~~
Main.cpp:172:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  172 |    mi=hi+lo>>1;
      |       ~~^~~

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