Submission #1085665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085665		Sunbae	Global Warming (NOI13_gw)	C++17	40 / 40	719 ms	29080 KiB

gw

#include <cstdio>
#include <set>
#include <algorithm>
#include <numeric>
#define z exit(0)
#define mp make_pair
#define F first
#define S second
using namespace std;
using pii = pair<int,int>;
const int N = 1e6, inf = 1e9;
int m, idx[N];
set<pii> s;
int gw(int n, int H[]){
	iota(idx, idx+n, 0);
	auto cmp = [&](int i, int j) { return (H[i] == H[j]) ? i < j : H[i] < H[j]; }; 
	sort(idx, idx+n, cmp);
	int mx = -inf;
	s.clear(); s.emplace(0, n-1);
	for(int j = 0, k = 0; j<n; ){
		for(k = j; k+1 < n && H[idx[k+1]] == H[idx[j]]; ++k){}
		for(int i = j; i<=k; ++i){
			auto itr = s.upper_bound(mp(idx[i], inf)); --itr;
			if(itr == s.end()) continue;
			int l = itr->F, r = itr->S;
			s.erase(itr);
			if(l <= idx[i]-1) s.emplace(l, idx[i]-1);
			if(idx[i]+1 <= r) s.emplace(idx[i]+1, r);
		}
		j = k+1; 
		mx = max(mx, (int)s.size());
	}
	return mx;
}

signed main(){
	int n; scanf("%d", &n);
	int H[n];
	for(int i = 0; i<n; ++i) scanf("%d", H+i);
	printf("%d", gw(n, H));
}	

Compilation message (stderr)

gw.cpp: In function 'int main()':
gw.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
gw.cpp:39:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  for(int i = 0; i<n; ++i) scanf("%d", H+i);
      |                           ~~~~~^~~~~~~~~~~

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