Submission #181626

---

Source Code Expand

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int n;
int x[60005];
vector<int>pos[120005];
int nxt[60005];
int f[60005];

#define s (1<<17)

int seg[s];
void update(int k,int a){
	k+=s/2-1; seg[k]=a;
	while(k>0){
		k=(k-1)/2;
		seg[k]=max(seg[k*2+1],seg[k*2+2]);
	}
}
int query(int a,int b,int k,int l,int r){
	if(r<a || b<l) return 0;
	if(a<=l && r<=b) return seg[k];
	else{
		int vl=query(a,b,k*2+1,l,(l+r)/2);
		int vr=query(a,b,k*2+2,(l+r)/2+1,r);
		return max(vl,vr);
	}
}
int seg2[s];
void update2(int k,int a){
	k+=s/2-1; seg2[k]=a;
	while(k>0){
		k=(k-1)/2;
		seg2[k]=min(seg2[k*2+1],seg2[k*2+2]);
	}
}
int query2(int a,int b,int k,int l,int r){
	if(r<a || b<l) return 1e9;
	if(a<=l && r<=b) return seg2[k];
	else{
		int vl=query2(a,b,k*2+1,l,(l+r)/2);
		int vr=query2(a,b,k*2+2,(l+r)/2+1,r);
		return min(vl,vr);
	}
}

bool cmp(const int& a,const int& b)
{
	if(nxt[a] != nxt[b]) return nxt[a] < nxt[b];
	return a > b;
}
int main()
{
	scanf("%d",&n);
	if(n > 60000) return 0;

	fill(seg2,seg2+(1<<17),1e9);
	
	for(int i=0;i<n;i++)
	{
		scanf("%d",&x[i]); update(i,x[i]); update2(i,x[i]);
		pos[x[i]-i+60000].push_back(i); f[i] = i;
	}
	fill(nxt,nxt+n,1e9);
	
	for(int i=0;i<=120000;i++)
	{
		if(pos[i].size()<=1) continue;
		
		for(int j=0;j<pos[i].size();j++)
		{
			for(int k=j+1;k<pos[i].size();k++)
			{
				int maxv = query(pos[i][j],pos[i][k],0,0,(1<<16)-1);
				int minv = query2(pos[i][j],pos[i][k],0,0,(1<<16)-1);
				if(maxv == x[pos[i][k]] && minv == x[pos[i][j]])
				{
					nxt[pos[i][j]] = pos[i][k];
					break;
				}
				if(minv != x[pos[i][j]) break;
			}
		}
	}
	sort(f,f+n,cmp);
	pair<int,int> las = make_pair(-1,-1);
	vector<pair<int,int> >res;
	
	for(int i=0;i<n;i++)
	{
		int x = f[i];
		if(nxt[x] == 1e9) break;
		if(las == make_pair(-1,-1))
		{
			res.push_back(make_pair(x,nxt[x]));
			las = make_pair(x,nxt[x]);
		}
		else if(min(nxt[x],las.second)-max(x,las.first) <= 2)
		{
			res.push_back(make_pair(x,nxt[x]));
			las = make_pair(x,nxt[x]);
		}
	}
	
	printf("%d\n",res.size());
	for(int i=0;i<res.size();i++) printf("%d %d\n",++res[i].first,++res[i].second);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:85:27: error: expected ‘]’ before ‘)’ token
./Main.cpp:109:26: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<std::pair<int, int> >::size_type {aka long unsigned int}’ [-Wformat]
./Main.cpp:58:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:65:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]