oj.uz

Submission #1085656

# Submission time Handle Problem Language Result Execution time Memory
1085656 2024-09-08T14:24:22 Z Sunbae Global Warming (NOI13_gw) C++17
29 / 40
 803 ms 29020 KB 
#include <cstdio>
#include <set>
#include <algorithm>
#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[]){
	s.clear();
	for(int i = 0, j = 0; i<n; ){
		for(; j+1<n && H[j+1] > 0; ++j){}
		s.emplace(i, j);
		i = j+2; j = i;
	}
	for(int i = 0; i<n; ++i) idx[i] = i;
	auto cmp = [&](int i, int j) { return (H[i] == H[j]) ? i < j : H[i] < H[j]; }; 
	sort(idx, idx+n, cmp);
	int mx = (int)s.size(), j = 0;
	for(int i = 0; i<n; ++i) if(H[idx[i]]){ j = i; break;}
	for(int k; 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

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

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2456 KB Output is correct
2 Correct 33 ms 2452 KB Output is correct
3 Correct 33 ms 2476 KB Output is correct
4 Correct 37 ms 2508 KB Output is correct
5 Correct 36 ms 2488 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3080 KB Output is correct
2 Correct 33 ms 4004 KB Output is correct
3 Correct 46 ms 3064 KB Output is correct
4 Correct 55 ms 3176 KB Output is correct
5 Correct 50 ms 3112 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 28896 KB Output is correct
2 Correct 729 ms 28820 KB Output is correct
3 Correct 748 ms 29004 KB Output is correct
4 Correct 694 ms 29020 KB Output is correct
5 Correct 695 ms 28388 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 792 ms 28508 KB Output is correct
2 Correct 803 ms 28668 KB Output is correct
3 Correct 760 ms 28620 KB Output is correct
4 Correct 424 ms 22744 KB Output is correct
5 Incorrect 403 ms 22788 KB Output isn't correct
6 Halted 0 ms 0 KB -