oj.uz

Submission #24676

# Submission time Handle Problem Language Result Execution time Memory
24676 2017-06-11T14:48:43 Z noobprogrammer Global Warming (NOI13_gw) C++14
40 / 40
 439 ms 17644 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17644 KB Output is correct
2 Correct 0 ms 17644 KB Output is correct
3 Correct 0 ms 17644 KB Output is correct
4 Correct 0 ms 17644 KB Output is correct
5 Correct 0 ms 17644 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 17644 KB Output is correct
2 Correct 26 ms 17644 KB Output is correct
3 Correct 33 ms 17644 KB Output is correct
4 Correct 23 ms 17644 KB Output is correct
5 Correct 23 ms 17644 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17644 KB Output is correct
2 Correct 16 ms 17644 KB Output is correct
3 Correct 36 ms 17644 KB Output is correct
4 Correct 33 ms 17644 KB Output is correct
5 Correct 36 ms 17644 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 17644 KB Output is correct
2 Correct 353 ms 17644 KB Output is correct
3 Correct 399 ms 17644 KB Output is correct
4 Correct 439 ms 17644 KB Output is correct
5 Correct 356 ms 17644 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 17644 KB Output is correct
2 Correct 353 ms 17644 KB Output is correct
3 Correct 356 ms 17644 KB Output is correct
4 Correct 263 ms 17644 KB Output is correct
5 Correct 313 ms 17644 KB Output is correct