oj.uz

Submission #99325

# Submission time Handle Problem Language Result Execution time Memory
99325 2019-03-02T15:28:42 Z TadijaSebez Railway Trip (JOI17_railway_trip) C++11
0 / 100
 162 ms 16816 KB 
#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);
		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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 162 ms 16504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 160 ms 16816 KB Output isn't correct
2 Halted 0 ms 0 KB -