Submission #1226710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226710		salmon	Railway Trip (JOI17_railway_trip)	C++20	0 / 100	2099 ms	125248 KiB

railway_trip

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

int N,Q;
int lst[200100];
vector<int> pos[200100];
pair<int,int> parent[25][400100][3];
int cost[25][400100][3];
int cont = 0;
map<pair<int,int>,int> mep;
int direc[200100][2];
int l[400100];
int r[400100];

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;

void cart(int l, int r){
	if(l > r) return;
	int it = cont;
	mep[{l,r}] = cont;
	::l[cont] = l;
	::r[cont] = r;
	cont++;
	
	if(l == r) return;
	if(l == r - 1) return;
	//printf("%d %d\n",l,r);
	if(l == 2 && r == 5) assert (1 == 2);
	int num = root -> query(l + 1, r - 1);
	
	int spos = lower_bound(pos[num].begin(), pos[num].end(), l )- pos[num].begin();
	int epos = lower_bound(pos[num].begin(),pos[num].end(), r) - pos[num].begin() - 1;

	for(int i = spos; i < epos; i++){
		if(i - spos == epos - (i + 1)){
			parent[0][cont][0] = {it,0};
			cost[0][cont][0] = i - spos + 1;
			
			parent[0][cont][1] = {it,1};
			cost[0][cont][1] = i - spos + 1;
			
			parent[0][cont][2] = {it,2};
			cost[0][cont][2] = i - spos + 1;
		}
		else if(i - spos + 1 == epos - (i + 1)){
			parent[0][cont][0] = {it,2};
			cost[0][cont][0] = i - spos + 1;
			
			parent[0][cont][1] = {it,0};
			cost[0][cont][1] = i - spos + 2;
			
			parent[0][cont][2] = {it,2};
			cost[0][cont][2] = i - spos + 1;
		}
		else if(i - spos == epos - (i + 1) + 1){
			parent[0][cont][0] = {it,1};
			cost[0][cont][0] = i - spos;
			
			parent[0][cont][1] = {it,1};
			cost[0][cont][1] = i - spos;
			
			parent[0][cont][2] = {it,0};
			cost[0][cont][2] = i - spos + 1;
		}
		else if(i - spos < epos - (i + 1)){
			int d = i-spos;
			
			parent[0][cont][0] = {it,2};
			cost[0][cont][0] = d;
			
			parent[0][cont][1] = {it,2};
			cost[0][cont][1] = d + 1;
			
			parent[0][cont][2] = {it,2};
			cost[0][cont][2] = d;
		}
		else{
			int d = epos - (i + 1);
			
			parent[0][cont][0] = {it,1};
			cost[0][cont][0] = d;
			
			parent[0][cont][1] = {it,1};
			cost[0][cont][1] = d;
			
			parent[0][cont][2] = {it,1};
			cost[0][cont][2] = d + 1;
		}
		
		cart(pos[num][i],pos[num][i+1]);
	}
	
	if(spos == epos){
		int d = 1;
		
		parent[0][cont][0] = {it,2};
		cost[0][cont][0] = d;
		
		parent[0][cont][1] = {it,0};
		cost[0][cont][1] = d + 1;
		
		parent[0][cont][2] = {it,2};
		cost[0][cont][2] = d;
		
		cart(l,pos[num][spos]);
		
		parent[0][cont][0] = {it,1};
		cost[0][cont][0] = d;
		
		parent[0][cont][1] = {it,1};
		cost[0][cont][1] = d;
		
		parent[0][cont][2] = {it,0};
		cost[0][cont][2] = d + 1;
		
		cart(pos[num][spos],r);
	}
	else{
		int d = 1;
		
		parent[0][cont][0] = {it,2};
		cost[0][cont][0] = d;
		
		parent[0][cont][1] = {it,0};
		cost[0][cont][1] = d + 1;
		
		parent[0][cont][2] = {it,2};
		cost[0][cont][2] = d;
		
		cart(l,pos[num][spos]);
		
		parent[0][cont][0] = {it,1};
		cost[0][cont][0] = d;
		
		parent[0][cont][1] = {it,1};
		cost[0][cont][1] = d;
		
		parent[0][cont][2] = {it,0};
		cost[0][cont][2] = d + 1;
		
		cart(pos[num][epos],r);
	}
	
}

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 = 0; i < 25; i++){
		for(int j = 1; j <= N; j++){
			parent[i][j][0] = {-1,-1};
			parent[i][j][1] = {-1,-1};
			parent[i][j][2] = {-1,-1};
		}
	}

	cart(1,N);

	for(int i = 1; i < 25; i++){
		for(int j = 1; j <= N; j++){
			for(int k = 0; k < 3; k++){
				if(parent[i - 1][j][k].first != -1){
					parent[i][j][k] = parent[i - 1][parent[i - 1][j][k].first][parent[i - 1][j][k].second];
					cost[i][j][k] = cost[i - 1][j][k] + cost[i - 1][parent[i - 1][j][k].first][parent[i - 1][j][k].second];
				}
			}
		}
	}
	
	for(int i = 0; i < Q; i++){
		int A,B;
		scanf(" %d",&A);
		scanf(" %d",&B);
		
		if(lst[B] <= lst[A]){
			int cont = 0;
			
			for(int i = min(A,B) + 1; i < max(A,B); i++){
				if(lst[i] >= lst[B]) cont++;
			}
			
			printf("%d\n",cont);
		}
		else{
			if(A < B){
				int cont = 0;
				
				int past = B;
				int va;
			
				for(int i = B - 1; i >= 1; i--){
					if(lst[i] >= lst[B]){
						if(i < A){
							va = i;
							break;
						}
						past = i;
						cont++;
					}
				}
				
				int co = mep[{va,past}];
				
				cont--;
				
				int ans;
				int c = mep[make_pair(direc[A][0],A)];
				int k = 1;
				int cos = 0;
				
				for(int i = 24; i >= 0; i--){
					if(parent[i][c][k].first != -1 && (l[parent[i][c][k].first] <= l[co] && r[co] <= r[parent[i][c][k].first]) ){
						cos += cost[i][c][k];
						
						int temp1 = parent[i][c][k].second;
						k = parent[i][c][k].first;
						c = temp1;
					}
				}
				
				if(k == 2) cos++;
				
				ans = cos;
				
				c = mep[make_pair(A,direc[A][1])];
				k = 2;
				cos = 0;
				
				for(int i = 24; i >= 0; i--){
					if(parent[i][c][k].first != -1 && (l[parent[i][c][k].first] <= l[co] && r[co] <= r[parent[i][c][k].first]) ){
						cos += cost[i][c][k];
						
						int temp1 = parent[i][c][k].second;
						k = parent[i][c][k].first;
						c = temp1;
						
						printf("%d %d %d %d\n",k,l[c],r[c],cos);
					}
				}
				
				if(k == 2) cos++;
				
				ans = min(ans,cos);
				
				printf("%d\n",ans + cont);
				
			}
			else{
				int cont = 0;
				
				int past = B;
				int va;
			
				for(int i = B + 1; i <= N; i++){
					if(lst[i] >= lst[B]){
						if(i < A){
							va = i;
							break;
						}
						past = i;
						cont++;
					}
				}
				
				int co = mep[{past,va}];
				
				cont--;
				
				int ans;
				int c = mep[make_pair(direc[A][0],A)];
				int k = 1;
				int cos = 0;
				
				for(int i = 24; i >= 0; i--){
					if(parent[i][c][k].first != -1 && (l[parent[i][c][k].first] <= l[co] && r[co] <= r[parent[i][c][k].first]) ){
						cos += cost[i][c][k];
						
						int temp1 = parent[i][c][k].second;
						k = parent[i][c][k].first;
						c = temp1;
					}
				}
				
				if(k == 1) cos++;
				
				ans = cos;
				
				c = mep[make_pair(A,direc[A][1])];
				k = 2;
				cos = 0;
				
				for(int i = 24; i >= 0; i--){
					if(parent[i][c][k].first != -1 && (l[parent[i][c][k].first] <= l[co] && r[co] <= r[parent[i][c][k].first]) ){
						cos += cost[i][c][k];
						
						int temp1 = parent[i][c][k].second;
						k = parent[i][c][k].first;
						c = temp1;
					}
				}
				
				if(k == 1) cos++;
				
				ans = min(ans,cos);
				
				printf("%d\n",ans + cont);
			}
			
		}
		
	}
	
	
	
	
	
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:181:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
railway_trip.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         scanf(" %d",&K);
      |         ~~~~~^~~~~~~~~~
railway_trip.cpp:183:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
railway_trip.cpp:186:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |                 scanf(" %d",&lst[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
railway_trip.cpp:239:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  239 |                 scanf(" %d",&A);
      |                 ~~~~~^~~~~~~~~~
railway_trip.cpp:240:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  240 |                 scanf(" %d",&B);
      |                 ~~~~~^~~~~~~~~~

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