Submission #99326

#	Time	Username	Problem	Language	Result	Execution time	Memory
99326		TadijaSebez	Railway Trip (JOI17_railway_trip)	C++11	100 / 100	349 ms	17392 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
const int N=100050;
const int L=18;
int a[N],S[N],c,mx[N][L],mn[N][L],n,k,q,s,t,m,l,r;
int main()
{
	scanf("%i %i %i",&n,&k,&q);
	for(int i=1;i<=n;i++) scanf("%i",&a[i]);
	for(int i=1;i<=n;i++){ while(c && a[S[c]]<a[i]) c--;mn[i][0]=c?S[c]:i;S[++c]=i;}c=0;
	for(int i=n;i>=1;i--){ while(c && a[S[c]]<a[i]) c--;mx[i][0]=c?S[c]:i;S[++c]=i;}c=0;
	for(int j=1;j<L;j++) for(int i=1;i<=n;i++)
	{
		mn[i][j]=min(mn[mn[i][j-1]][j-1],mn[mx[i][j-1]][j-1]);
		mx[i][j]=max(mx[mn[i][j-1]][j-1],mx[mx[i][j-1]][j-1]);
	}
	while(q--)
	{
		scanf("%i %i",&s,&t);
		if(s>t) swap(s,t);
		int ans=0;
		l=r=s;
		for(int j=L-1;~j;j--) if(max(mx[l][j],mx[r][j])<t)
		{
			ans+=1<<j;
			tie(l,r)=mp(min(mn[l][j],mn[r][j]),max(mx[l][j],mx[r][j]));
		}
		m=r;l=r=t;
		for(int j=L-1;~j;j--) if(min(mn[l][j],mn[r][j])>m)
		{
			ans+=1<<j;
			tie(l,r)=mp(min(mn[l][j],mn[r][j]),max(mx[l][j],mx[r][j]));
		}
		printf("%i\n",ans);
	}
	return 0;
}

Compilation message (stderr)

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&k,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:10: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("%i",&a[i]);
                        ~~~~~^~~~~~~~~~~~
railway_trip.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&s,&t);
   ~~~~~^~~~~~~~~~~~~~~

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