Submission #290675

#	Time	Username	Problem	Language	Result	Execution time	Memory
290675		maximath_1	Railway Trip (JOI17_railway_trip)	C++11	100 / 100	226 ms	17272 KiB

railway_trip

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <string.h>
#include <set>
#include <math.h>
#include <numeric>
#include <assert.h>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <queue>
using namespace std;
#define ll long long
#define ld long double
#define endl "\n"
const ll inf = 1e9 + 69;
const ld pi = 3.14159265358979323L;
const ld eps = 1e-15;
const int N = 1e5 + 5;

void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
void setIO(string s = ""){
	unsyncIO();
	if(s.size()){
		setIn(s + ".in");
		setOut(s + ".out");
	}
}

int n, k, q, v[100005];
int ancL[100005][18], ancR[100005][18];

int main(){
	setIO();

	cin >> n >> k >> q;
	for(int i = 1; i <= n; i ++) cin >> v[i];

	for(int i = 1; i <= n; i ++){
		ancL[i][0] = i - 1;
		while(ancL[i][0] >= 1 && v[ancL[i][0]] < v[i])
			ancL[i][0] = ancL[ancL[i][0]][0];
	}
	ancL[0][0] = 1;

	for(int i = n; i >= 1; i --){
		ancR[i][0] = i + 1;
		while(ancR[i][0] <= n && v[ancR[i][0]] < v[i])
			ancR[i][0] = ancR[ancR[i][0]][0];
	}
	ancR[n][0] = n;

	for(int j = 1; j < 18; j ++){
		for(int i = 1; i <= n; i ++){
			ancL[i][j] = min(ancL[ancL[i][j - 1]][j - 1], ancL[ancR[i][j - 1]][j - 1]);
			ancR[i][j] = max(ancR[ancL[i][j - 1]][j - 1], ancR[ancR[i][j - 1]][j - 1]);
		}
	}

	for(int u, v; q --;){
		cin >> u >> v; if(u > v) swap(u, v);
		int ans = 0, c;
		int l = u, r = u;
		for(int i = 17; i >= 0; i --){
			if(max(ancR[l][i], ancR[r][i]) < v){
				int tl = min(ancL[l][i], ancL[r][i]);
				int tr = max(ancR[l][i], ancR[r][i]);
				l = tl, r = tr;
				ans += (1 << i);
			}
		}

		c = r;
		l = v, r = v;
		for(int i = 17; i >= 0; i --){
			if(min(ancL[l][i], ancL[r][i]) > c){
				int tl = min(ancL[l][i], ancL[r][i]);
				int tr = max(ancR[l][i], ancR[r][i]);
				l = tl, r = tr;
				ans += (1 << i);
			}
		}

		cout << ans << endl;
	}

	return 0;
}

Compilation message (stderr)

railway_trip.cpp: In function 'void setIn(std::string)':
railway_trip.cpp:25:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   25 | void setIn(string s){freopen(s.c_str(), "r", stdin);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp: In function 'void setOut(std::string)':
railway_trip.cpp:26:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   26 | void setOut(string s){freopen(s.c_str(), "w", stdout);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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