oj.uz

Submission #873526

# Submission time Handle Problem Language Result Execution time Memory
873526 2023-11-15T09:01:35 Z dsyz Global Warming (NOI13_gw) C++17
19 / 40
 191 ms 41096 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 460 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 16 ms 3796 KB Output is correct
2 Correct 16 ms 3796 KB Output is correct
3 Correct 19 ms 3708 KB Output is correct
4 Correct 17 ms 3968 KB Output is correct
5 Correct 16 ms 3972 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4564 KB Output is correct
2 Correct 12 ms 4308 KB Output is correct
3 Correct 18 ms 4296 KB Output is correct
4 Correct 21 ms 4748 KB Output is correct
5 Correct 17 ms 4300 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 191 ms 41096 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 185 ms 40360 KB Memory limit exceeded
2 Halted 0 ms 0 KB -