Submission #24676

#	Time	Username	Problem	Language	Result	Execution time	Memory
24676		noobprogrammer	Global Warming (NOI13_gw)	C++14	40 / 40	439 ms	17644 KiB

gw

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define ii pair<int,int>
#define vii vector<pair<int,int> >
#define vi vector<int>

int n , par[1000010] , arr[1000010] ;
ii pos[1000010] ;

int find_root(int x){
	if(par[x] == x) return x ;
	return par[x] = find_root(par[x]) ;
}

int main(){
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
	scanf("%d",&n) ;
	for(int i=1;i<=n;i++){
		scanf("%d",arr+i) ;
		pos[i] = {arr[i] , i} ;
		par[i] = i ;
	}
	sort(pos+1 , pos+n+1) ;
	int px , py , cur , j , idx , num = 0 , res = 0 ;
	for(int i = n ; i> 0 ;){
		j = i ; cur = pos[i].fi ;
		while(pos[j].fi == cur){
			num++ ;
			j-- ;
		}
		while(i>j){
			idx = pos[i].se ;
			if(arr[idx - 1] >= cur ){
				px = find_root(idx) ; py = find_root(idx-1) ;
				if(px != py){
					num-- ;
					par[py] = px ;
				}
			}
			if(arr[idx + 1] >= cur ){
				px = find_root(idx) ; py = find_root(idx+1) ;
				if(px != py){
					num-- ;
					par[py] = px ;
				}
			}
			i-- ;
		}
		res = max( res , num ) ;
	}
	printf("%d",res) ;
	return 0;
}

Compilation message (stderr)

gw.cpp: In function 'int main()':
gw.cpp:21:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n) ;
                 ^
gw.cpp:23:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",arr+i) ;
                     ^

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11