Submission #76724

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#define REP(i,m) for(int i=0;i<m;++i)
#define REPN(i,m,in) for(int i=in;i<m;++i)
#define ALL(t) (t).begin(),(t).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
using namespace std;
static const int INF =500000000; 
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef long long int lint;
typedef pair<int,int> pi;
int n;
int a[1100005];
pi res[1100005];
bool judge(const pi& a){
	return a.fr==-1;
}
struct RMQ{
	int mini[18][60005],maxi[18][60005];
	int loga[60005],powe[60005];
	void init(){
		REP(i,n) mini[0][i]=maxi[0][i]=a[i];
		REP(i,17) REP(j,n){
			if(j+(1<<i)>=n){
				mini[i+1][j]=mini[i][j];
				maxi[i+1][j]=maxi[i][j];
			}else{
				mini[i+1][j]=min(mini[i][j],mini[i][j+(1<<i)]);
				maxi[i+1][j]=max(maxi[i][j],maxi[i][j+(1<<i)]);
			}
		}
		REP(i,60005){
			loga[i]=0;
			while((1<<loga[i])*2<=i) ++loga[i];
			powe[i]=(1<<loga[i]);
		}
	}
	int query_min(int a,int b){//[a,b)
		int len=b-a;
		return min(mini[loga[len]][a],mini[loga[len]][b-powe[len]]);
	}
	int query_max(int a,int b){
		int len=b-a;
		return max(maxi[loga[len]][a],maxi[loga[len]][b-powe[len]]);
	}
};
RMQ rmq;
int rev[1100005];

int main(){
	scanf("%d",&n);
	REP(i,n) scanf("%d",&a[i]),rev[a[i]]=i;
	int m=0;
	if(n<=3000){

		REP(i,n) {
			int mini=a[i],maxi=a[i];
			REPN(j,n,i){
				mini=min(mini,a[j]);
				maxi=max(maxi,a[j]);
				if(i!=j && maxi==a[j] && mini==a[i] && maxi-mini==j-i){
					res[m++]=mp(i,j);
					break;
				}
				if(mini<a[i]) break;
			}
		}
	}else{
		rmq.init();
		REP(i,n) {
			int mini=a[i],maxi=a[i];
			int j=i+1;
			while(j<n){
				mini=rmq.query_min(i,j+1);
				maxi=rmq.query_max(i,j+1);
				if(mini<a[i]) break;
				if(maxi==a[j] && maxi-mini==j-i){
					res[m++]=mp(i,j);
					break;
				}
				if(maxi+1>=n) break;
				j=rev[maxi+1];
			}
		}
	}
	reverse(res,res+m);
	int mini=INF;
	REP(i,m){
		if(mini<=res[i].sc) res[i]=mp(-1,-1);
		else mini=min(mini,res[i].sc);
	}
	reverse(res,res+m);
	m=remove_if(res,res+m,judge)-res;


	printf("%d\n",m);
	REP(i,m) printf("%d %d\n",res[i].fr+1,res[i].sc+1);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:59:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:60:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result