Submission #181625


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++)
			{
				if(query(pos[i][j],pos[i][k],0,0,(1<<16)-1) == x[pos[i][k]] && query2(pos[i][j],pos[i][k],0,0,(1<<16)-1) == x[pos[i][j]])
				{
					nxt[pos[i][j]] = pos[i][k];
					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

Submission Time
Task 15 - Empodia
User IH19980412
Language C++ (G++ 4.6.4)
Score 65
Code Size 2183 Byte
Status WA
Exec Time 1035 ms
Memory 6688 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:106: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]

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 0 / 5 0 / 5 0 / 5 0 / 5 5 / 5 5 / 5 0 / 5 0 / 5 0 / 5
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
TLE × 1
TLE × 1
TLE × 1
TLE × 1
AC × 1
AC × 1
TLE × 1
TLE × 1
WA × 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 28 ms 4256 KB
02 AC 325 ms 4252 KB
03 AC 325 ms 4136 KB
04 AC 55 ms 4192 KB
05 AC 42 ms 4136 KB
06 AC 42 ms 4256 KB
07 AC 47 ms 4208 KB
08 AC 30 ms 4248 KB
09 AC 35 ms 4212 KB
10 AC 37 ms 4140 KB
11 AC 71 ms 6688 KB
12 TLE 1029 ms 5548 KB
13 TLE 1030 ms 5544 KB
14 TLE 1029 ms 5536 KB
15 TLE 1032 ms 5492 KB
16 AC 800 ms 5472 KB
17 AC 261 ms 5540 KB
18 TLE 1035 ms 5152 KB
19 TLE 1030 ms 5288 KB
20 WA 26 ms 3500 KB