Submission #335278

#	Time	Username	Problem	Language	Result	Execution time	Memory
335278		Plurm	Railway Trip (JOI17_railway_trip)	C++11	15 / 100	2066 ms	12524 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
vector<int> g[100005]; // cartesian-tree-like graph
int d[100005];
vector<int> bckt[100005];
int l[100005];
int n,k,q;
void compute(int a){
	d[a] = 0;
	for(int i = 1; i <= k; i++){
		for(int x : bckt[i]){
			for(int y : g[x]) d[x] = min(d[x], d[y]+1);
		}
		reverse(bckt[i].begin(), bckt[i].end());
		for(int x : bckt[i]){
			for(int y : g[x]) d[x] = min(d[x], d[y]+1);
		}
		reverse(bckt[i].begin(), bckt[i].end());
	}
}
int main(){
	scanf("%d%d%d",&n,&k,&q);
	stack<int> stk;
	for(int i = 1; i <= n; i++){
		scanf("%d", l+i);
		bckt[l[i]].push_back(i);
		while(!stk.empty() && l[stk.top()] <= l[i]){
			g[i].push_back(stk.top());
			stk.pop();
		}
		if(!stk.empty() && l[stk.top()] == l[i]) g[i].push_back(stk.top());
		stk.push(i);
	}
	while(!stk.empty()) stk.pop();
	for(int i = n; i > 0; i--){
		while(!stk.empty() && l[stk.top()] <= l[i]){
			g[i].push_back(stk.top());
			stk.pop();
		}
		if(!stk.empty() && l[stk.top()] == l[i]) g[i].push_back(stk.top());
		stk.push(i);
	}
	while(q--){
		int a,b;
		scanf("%d%d",&a,&b);
		for(int i = 1; i <= n; i++) d[i] = 1e9;
		compute(a);
		vector<int> v(n);
		for(int i = 1; i <= n; i++) v[i] = d[i];
		for(int i = 1; i <= n; i++) d[i] = 1e9;
		compute(b);
		int ans = 1e9;
		for(int i = 1; i <= n; i++){
			ans = min(ans, v[i] + d[i]);
		}
		printf("%d\n", ans-1);
	}
	return 0;
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf("%d%d%d",&n,&k,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
railway_trip.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   scanf("%d", l+i);
      |   ~~~~~^~~~~~~~~~~
railway_trip.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

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