Submission #1085618

#TimeUsernameProblemLanguageResultExecution timeMemory
1085618SunbaeGlobal Warming (NOI13_gw)C++17
19 / 40
1010 ms65536 KiB
#include <bits/stdc++.h> #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 + 5, inf = 1e9; int cp[N], a[N], m; set<pii> s; vector<int> to_remove[N]; int gw(int n, int H[]){ for(int i = m = 0; i<n; ++i) cp[m++] = H[i]; cp[m++] = 0; for(int i = 0; i<m; ++i) to_remove[i].clear(); sort(cp, cp+m); m = unique(cp, cp+m) - cp; for(int i = 0; i<n; ++i) to_remove[a[i] = lower_bound(cp, cp+m, H[i]) - cp].push_back(i); for(int i = 0, j = 0; i<n; ){ for(; j<n && a[j+1] > 0; ++j){} s.emplace(i, j); i = j+2; j = i; } int mx = (int)s.size(); for(int t = 1; t<m; ++t){ for(int j : to_remove[t]){ set<pii>::iterator itr = (--s.upper_bound(mp(j, inf))); if(itr == s.end()) continue; int l = itr->F, r = itr->S; s.erase(itr); if(l <= j-1) s.emplace(l, j-1); if(j+1 <= r) s.emplace(j+1, r); } 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:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
gw.cpp:40:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  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...