Submission #1101840

#TimeUsernameProblemLanguageResultExecution timeMemory
1101840blackslexGlobal Warming (NOI13_gw)C++17
19 / 40
520 ms65536 KiB
#include<bits/stdc++.h> using namespace std; using pii = pair<int, int>; int n; int main() { scanf("%d", &n); vector<int> a(n), par(n); iota(par.begin(), par.end(), 0); vector<bool> ck(n); for (auto &e: a) scanf("%d", &e); int cnt = 0, ans = 0; function<int(int)> fset = [&] (int x) {return (par[x] == x ? x : par[x] = fset(par[x]));}; auto mg = [&] (int x, int y) { if ((x = fset(x)) == (y = fset(y))) return; if (ck[x] && ck[y]) cnt--, par[x] = y; else if (!ck[x] && !ck[y]) cnt++, par[y] = x; else par[y] = x; ck[x] = ck[y] = 1; }; vector<int> c = a; sort(c.begin(), c.end()); c.resize(unique(c.begin(), c.end()) - c.begin()); vector<vector<int>> add(n, vector<int>()); auto get = [&] (int x) { return lower_bound(c.begin(), c.end(), x) - c.begin(); }; for (int i = 0; i < n; i++) add[get(a[i])].emplace_back(i); for (int i = n - 1; i >= 0; i--) { for (auto &e: add[i]) { if (e && a[e - 1] >= a[e]) mg(e - 1, e); if (e != n - 1 && a[e + 1] >= a[e]) mg(e, e + 1); if (!ck[e]) cnt++, ck[e] = 1; } ans = max(ans, cnt); } printf("%d", ans); }

Compilation message (stderr)

gw.cpp: In function 'int main()':
gw.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
gw.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     for (auto &e: a) scanf("%d", &e);
      |                      ~~~~~^~~~~~~~~~
#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...