Submission #1249044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249044		_rain_	Railway Trip (JOI17_railway_trip)	C++20	100 / 100	82 ms	17352 KiB

railway_trip

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

const int N = (int)1e5;
const int MAXLOG = (int)17;
	int a[N+2] , b[N+2] ,l[N+2];
	int lef[N+2][MAXLOG+2] , rig[N+2][MAXLOG+2];
	int n,k,q;
	
	void process(int l,int r){
		if (l>r) swap(l,r);
		int ans = 0;
		int t_l , t_r;
		t_l = t_r = l;
		for(int j = MAXLOG; j >= 0; --j){
			int nxt_r = max(rig[t_l][j] , rig[t_r][j]);
			int nxt_l = min(lef[t_l][j] , lef[t_r][j]);
			if (nxt_r < r){
				t_r = nxt_r , t_l = nxt_l;
				ans += (1<<j);
			}
		}
		l = t_r;
//		cout<<l<<' '<<ans<<'\n';
		t_l = t_r = r;
		for(int j = MAXLOG; j >= 0; --j){
			int nxt_r = max(rig[t_l][j] , rig[t_r][j]);
			int nxt_l = min(lef[t_l][j] , lef[t_r][j]);
			if (nxt_l > l){
				t_r = nxt_r , t_l = nxt_l;
				ans += (1<<j);
			}
		}
		cout<<ans<<'\n';
	}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
		}
		
		cin>>n>>k>>q;
		for(int i = 1; i <= n; ++i) cin>>l[i];
		for(int i = 1; i <= q; ++i) cin>>a[i]>>b[i];
		vector<int>st;
		for(int i = 1; i <= n; ++i) {
			while (st.size() && l[st.back()] < l[i]) st.pop_back();
			if (st.size()) lef[i][0] = st.back(); else lef[i][0] = i;
			st.push_back(i);
		}
		st.clear();
		for(int i = n; i >= 1; --i) {
			while (st.size() && l[st.back()] < l[i]) st.pop_back();
			if (st.size()) rig[i][0] = st.back(); else rig[i][0] = i;
			st.push_back(i);
		}
		
//		for(int i = 1; i <= n; ++i) cout<<i<<' '<<lef[i][0]<<' '<<rig[i][0]<<'\n';
		
		for(int j = 1; j <= MAXLOG; ++j) {
			for(int i = 1; i <= n; ++i) {
				int l = min(lef[lef[i][j-1]][j-1],lef[rig[i][j-1]][j-1]);
				int r = max(rig[lef[i][j-1]][j-1],rig[rig[i][j-1]][j-1]);
				lef[i][j] = l , rig[i][j] = r;
			}
		}
		for(int i = 1; i <= q; ++i) process(a[i] , b[i]);
		return 0;
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:43:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55