Submission #1227859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227859		salmon	Railway Trip (JOI17_railway_trip)	C++20	100 / 100	198 ms	38556 KiB

railway_trip

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

int N,Q;
int lst[200100];
vector<int> pos[200100];
int l[25][200100];
int r[25][200100];
map<pair<int,int>,int> mep;
int direc[200100][2];

struct node{	
	
	int s, e, m;
	int v;
	node *l, *r;
	
	node(int S, int E){
		s = S;
		e = E;
		m = (s + e)/2;
		
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1, e);
			v = max(l -> v, r -> v);
		}
		else{
			v = lst[s];
		}
	}	
	
	int query(int S, int E){
		if(S <= s && e <= E) return v;
		
		int V = 0;
		
		if(S <= m) V = max(V, l -> query(S,E));
		if(m < E) V = max(V, r -> query(S,E)) ;
		
		return V;
	}
}*root;


int main(){
	
	int K;
	
	scanf(" %d",&N);
	scanf(" %d",&K);
	scanf(" %d",&Q);
	
	for(int i = 1; i <= N; i++){
		scanf(" %d",&lst[i]);
		if(i != 1 && i != N) pos[lst[i]].push_back(i);
	}	

	vector<int> steck = {1};
	
	direc[1][0] = -1;
	
	for(int i = 2; i <= N; i++){
		while(lst[steck.back()] < lst[i]) steck.pop_back();
		
		direc[i][0] = steck.back();
		
		steck.push_back(i);
	}
	
	direc[N][1] = -1;
	
	steck = {N};
	
	for(int i = N - 1; i >= 1; i--){
		while(lst[steck.back()] < lst[i]) steck.pop_back();
		
		direc[i][1] = steck.back();
		
		steck.push_back(i);
	}
	
	root = new node(1,N);

	for(int i = 1; i <= N; i++){
		l[0][i] = max(1,direc[i][0]);
		r[0][i] = min(N,direc[i][1]);
	}
	
	r[0][N] = N;

	for(int j = 1; j < 25; j++){
	for(int i = 1; i <= N; i++){
		l[j][i] = min(l[j - 1][l[j - 1][i]], l[j - 1][r[j - 1][i]]);
		r[j][i] = max(r[j - 1][l[j - 1][i]], r[j - 1][r[j - 1][i]]);
	}
	}
	
	for(int i = 0; i < Q; i++){
		int A, B;
		scanf(" %d",&A);
		scanf(" %d",&B);
		
		int num = 0;
		
		int l1, r1;
		
		l1 = A;
		r1 = A;
		
		for(int j = 24; j >= 0; j--){
			if(max(r[j][l1], r[j][r1]) < B || B < min(l[j][l1], l[j][r1])){
				int temp = min(l[j][l1], l[j][r1]);
				r1 = max(r[j][l1], r[j][r1]);
				l1 = temp;
				num += (1<<j);
			}
		}
		int l2,r2;
		
		l2 = B;
		r2 = B;
		
		for(int j = 24; j >= 0; j--){
			if(max(r[j][l2], r[j][r2]) < l1 || r1 < min(l[j][l2], l[j][r2])){
				int temp = min(l[j][l2], l[j][r2]);
				r2 = max(r[j][l2], r[j][r2]);
				l2 = temp;
				num += (1<<j);
			}
		}
		
		printf("%d\n",num + 1 - 1);
	}
	
	
	
	
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
railway_trip.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf(" %d",&K);
      |         ~~~~~^~~~~~~~~~
railway_trip.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
railway_trip.cpp:55:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |                 scanf(" %d",&lst[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
railway_trip.cpp:101:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |                 scanf(" %d",&A);
      |                 ~~~~~^~~~~~~~~~
railway_trip.cpp:102:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |                 scanf(" %d",&B);
      |                 ~~~~~^~~~~~~~~~

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