oj.uz

Submission #873527

# Submission time Handle Problem Language Result Execution time Memory
873527 2023-11-15T09:02:49 Z dsyz Global Warming (NOI13_gw) C++17
40 / 40
 204 ms 25716 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	ll arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
	}
	vector<pair<ll,ll> > sweepline;
	for(ll i = 0;i < N;i++){
		sweepline.push_back(make_pair(arr[i],i));
	}
	sort(sweepline.begin(),sweepline.end());
	ll sum = 1;
	ll islands = 1;
	ll abovewater[N];
	for(ll i = 0;i < N;i++){
		abovewater[i] = 1;
	}
	for(ll i = 0;i < N && N != 1;i++){
		if(sweepline[i].second == 0){
			if(abovewater[sweepline[i].second + 1] == 0){
				islands--;
				abovewater[sweepline[i].second] = 0;
			}else{
				abovewater[sweepline[i].second] = 0;
			}
		}else if(sweepline[i].second == N - 1){
			if(abovewater[sweepline[i].second - 1] == 0){
				islands--;
				abovewater[sweepline[i].second] = 0;
			}else{
				abovewater[sweepline[i].second] = 0;
			}
		}else{
			abovewater[sweepline[i].second] = 0;
			if(abovewater[sweepline[i].second - 1] == 0 && abovewater[sweepline[i].second + 1] == 0){
				islands--;
			}else if(abovewater[sweepline[i].second - 1] == 1 && abovewater[sweepline[i].second + 1] == 1){
				islands++;
			}
		}
		if(i != N - 1 && sweepline[i + 1].first == sweepline[i].first){
			continue;
		}
		sum = max(sum,islands);
	}
	cout<<sum<<'\n';
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2012 KB Output is correct
2 Correct 15 ms 1936 KB Output is correct
3 Correct 15 ms 1992 KB Output is correct
4 Correct 15 ms 2012 KB Output is correct
5 Correct 15 ms 2012 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2012 KB Output is correct
2 Correct 11 ms 2012 KB Output is correct
3 Correct 16 ms 2012 KB Output is correct
4 Correct 16 ms 2012 KB Output is correct
5 Correct 15 ms 2000 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 15972 KB Output is correct
2 Correct 174 ms 25716 KB Output is correct
3 Correct 178 ms 25528 KB Output is correct
4 Correct 181 ms 25524 KB Output is correct
5 Correct 178 ms 24756 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 16056 KB Output is correct
2 Correct 204 ms 25016 KB Output is correct
3 Correct 182 ms 24760 KB Output is correct
4 Correct 160 ms 18868 KB Output is correct
5 Correct 172 ms 19000 KB Output is correct