Submission #873527

#	Time	Username	Problem	Language	Result	Execution time	Memory
873527		dsyz	Global Warming (NOI13_gw)	C++17	40 / 40	204 ms	25716 KiB

gw

#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 / 6
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11