Submission #158013


Source Code Expand

#include <bits/stdc++.h>

#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define lli long long int
#define foreach( gg,itit )	for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
#define FP( ii,aa,bb ) for( int ii=aa;ii<=bb;ii++ )
#define FM( ii,aa,bb ) for( int ii=aa;ii>=bb;ii-- )

#define orta (bas+son)/2
#define sol root*2,bas,orta
#define sag root*2+1,orta+1,son

#define maxn 1100000

using namespace std;

int n,arr[maxn],buyuk[maxn],kucuk[maxn],a[maxn],b[maxn];
vector<int>	g[2*maxn];

void updatek( int ind,int x ){
	while( x<maxn ){
		kucuk[x] = min( kucuk[x],ind );
		x += x&-x;
	}
}
int queryk( int x ){
	int r = n+1;
	while( x ){
		r = min( r,kucuk[x] );
		x -= x&-x;
	}
	return r;
}

void updateb( int ind,int x ){
	while( x ){
		buyuk[x] = max( buyuk[x],ind );
		x -= x&-x;
	}
}
int queryb( int x ){
	int r = 0;
	while( x<maxn ){
		r = max( r,buyuk[x] );
		x += x&-x;
	}
	return r;
}

int main(){

	scanf("%d",&n);
	FP( i,1,n ){
		scanf("%d",arr+i);
		arr[i]++;
		g[arr[i]-i+maxn].pb(i);
	}
	
	memset( kucuk,30,sizeof kucuk );
	FM( i,n,1 ){
		a[i] = queryk( arr[i] )-1;
		updatek( i,arr[i] );
	}
	
	FP( i,1,n ){
		b[i] = queryb( arr[i] )+1;
		updateb( i,arr[i] );
	}
	vector< pair<int,int> >	v,r;
	
	FP( c,-n,n ){

		if( g[c+maxn].size()<2 )	continue;
		int ind=0,size=g[c+maxn].size();
		FP( i,1,size )	arr[i] = g[c+maxn][i-1];
		
		FP( i,1,size ){
			ind = max( ind,i+1 );
			while( ind<=size and b[arr[ind]]>arr[i] )	ind++;
			if( ind<=size and b[arr[ind]]<=arr[i] and a[arr[i]]>=arr[ind] )	v.pb( mp( arr[i],arr[ind] ) );
		}
		
	}
	
	sort( v.begin(),v.end() );
	
	foreach( v,it ){
		while( r.size() and r.back().nd>=it->nd )	r.pop_back();
		r.pb( *it );
	}
	
	cout << r.size() << endl;
	
	foreach( r,it )
		printf("%d %d\n",it->st,it->nd);
	
}

Submission Info

Submission Time
Task 15 - Empodia
User enesoncu
Language C++ (G++ 4.6.4)
Score 100
Code Size 1903 Byte
Status AC
Exec Time 807 ms
Memory 83252 KB

Compile Error

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

Judge Result

Set Name Set01 Set02 Set03 Set04 Set05 Set06 Set07 Set08 Set09 Set10 Set11 Set12 Set13 Set14 Set15 Set16 Set17 Set18 Set19 Set20
Score / Max Score 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5 5 / 5
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
Set01 01
Set02 02
Set03 03
Set04 04
Set05 05
Set06 06
Set07 07
Set08 08
Set09 09
Set10 10
Set11 11
Set12 12
Set13 13
Set14 14
Set15 15
Set16 16
Set17 17
Set18 18
Set19 19
Set20 20
Case Name Status Exec Time Memory
01 AC 158 ms 57408 KB
02 AC 149 ms 57408 KB
03 AC 144 ms 57396 KB
04 AC 144 ms 57404 KB
05 AC 148 ms 57276 KB
06 AC 162 ms 57276 KB
07 AC 149 ms 57264 KB
08 AC 146 ms 57404 KB
09 AC 142 ms 57400 KB
10 AC 145 ms 57400 KB
11 AC 168 ms 59580 KB
12 AC 166 ms 58544 KB
13 AC 166 ms 58428 KB
14 AC 167 ms 58424 KB
15 AC 169 ms 58436 KB
16 AC 166 ms 58436 KB
17 AC 170 ms 58684 KB
18 AC 161 ms 58044 KB
19 AC 165 ms 58296 KB
20 AC 807 ms 83252 KB