# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1101842 | 2024-10-17T02:50:50 Z | blackslex | Global Warming (NOI13_gw) | C++17 | 221 ms | 28088 KB |
#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<pii> c; for (int i = 0; i < n; i++) c.emplace_back(a[i], i); sort(c.begin(), c.end()); for (int i = n - 1; i >= 0; i--) { int e = c[i].second; 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; if (i != n - 1 && c[i].first == c[i + 1].first) continue; ans = max(ans, cnt); } printf("%d", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 336 KB | Output is correct |
2 | Correct | 1 ms | 336 KB | Output is correct |
3 | Correct | 1 ms | 336 KB | Output is correct |
4 | Correct | 1 ms | 336 KB | Output is correct |
5 | Correct | 1 ms | 336 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 18 ms | 2248 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 2248 KB | Output is correct |
2 | Correct | 12 ms | 2248 KB | Output is correct |
3 | Correct | 19 ms | 2248 KB | Output is correct |
4 | Correct | 20 ms | 2376 KB | Output is correct |
5 | Correct | 19 ms | 2252 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 221 ms | 28084 KB | Output is correct |
2 | Correct | 220 ms | 28088 KB | Output is correct |
3 | Correct | 211 ms | 28088 KB | Output is correct |
4 | Correct | 210 ms | 28088 KB | Output is correct |
5 | Correct | 198 ms | 27300 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 207 ms | 18612 KB | Output is correct |
2 | Correct | 216 ms | 27288 KB | Output is correct |
3 | Correct | 216 ms | 27320 KB | Output is correct |
4 | Correct | 193 ms | 21532 KB | Output is correct |
5 | Correct | 200 ms | 21432 KB | Output is correct |