Submission #72711

#	Time	Username	Problem	Language	Result	Execution time	Memory
72711		ikura355	Railway Trip (JOI17_railway_trip)	C++14	20 / 100	2073 ms	20616 KiB

railway_trip

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

const int maxn = 1e5 + 5;
const int inf = 1e9;

int n,k,m;
int a[maxn];
int st[maxn], ft[maxn];

int dq[maxn], len[maxn];
vector<int> way[maxn];
queue<int> q;

void init() {
	int sz = 0;
	for(int x=1;x<=n;x++) {
		int l = 1, r = sz, mid, pos = -1;
		while(l<=r) {
			mid = (l+r)/2;
			if(a[x] <= a[dq[mid]]) {
				pos = dq[mid];
				l = mid+1;
			}
			else r = mid-1;
		}
		if(pos!=-1) {
			way[pos].push_back(x);
			way[x].push_back(pos);
//			printf("%d - %d\n",x,pos);
		}
		dq[++sz] = x;
		while(sz>=2 && a[dq[sz-1]] <= a[dq[sz]]) dq[sz-1] = dq[sz], sz--;
	}
	sz = 0;
	for(int x=n;x>=1;x--) {
		int l = 1, r = sz, mid, pos = -1;
		while(l<=r) {
			mid = (l+r)/2;
			if(a[x] <= a[dq[mid]]) {
				pos = dq[mid];
				l = mid+1;
			}
			else r = mid-1;
		}
		if(pos!=-1) {
			way[pos].push_back(x);
			way[x].push_back(pos);
//			printf("%d - %d\n",x,pos);
		}
		dq[++sz] = x;
		while(sz>=2 && a[dq[sz-1]] <= a[dq[sz]]) dq[sz-1] = dq[sz], sz--;
	}
}
int solve(int x, int y) {
	for(int i=1;i<=n;i++) len[i] = inf;
	len[x] = 0;
	q.push(x);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(auto v : way[u]) {
			if(len[v] > len[u] + 1) {
				len[v] = len[u] + 1;
				q.push(v);
			}
		}
	}
	return len[y] - 1;
}
int main() {
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d%d",&st[i],&ft[i]);
	init();
	for(int i=1;i<=m;i++) printf("%d\n",solve(st[i],ft[i]));
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&k,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
railway_trip.cpp:72:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
                        ~~~~~^~~~~~~~~~~~
railway_trip.cpp:73:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%d%d",&st[i],&ft[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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