Submission #1085662

#TimeUsernameProblemLanguageResultExecution timeMemory
1085662SunbaeGlobal Warming (NOI13_gw)C++17
29 / 40
721 ms29072 KiB
#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[]){ 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; } 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 = (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 (stderr)

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