Submission #1113172

#TimeUsernameProblemLanguageResultExecution timeMemory
1113172votranngocvyGlobal Warming (NOI13_gw)C++14
40 / 40
208 ms20008 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fi first #define se second const int N = 1e6 + 5; int par[N],sz[N],f[N]; pii a[N]; void make_set(int v) { par[v] = v; sz[v] = 1; } int find_set(int v) { if (v == par[v]) return v; int p = find_set(par[v]); par[v] = p; return p; } void union_sets(int a,int b) { a = find_set(a),b = find_set(b); if (a == b) return; if (sz[a] < sz[b]) swap(a,b); sz[a] += sz[b]; par[b] = a; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].fi; a[i].se = i; } sort(a + 1,a + n + 1,greater<pii>()); for (int i = 1; i <= n; i++) make_set(i); int ans = 0,cnt = 0,i = 1; while (i <= n) { int j = i; while (j <= n && a[j].fi == a[i].fi) { cnt++; if (j > 1 && f[a[j].se - 1]) { union_sets(a[j].se - 1,a[j].se); cnt--; } if (j < n && f[a[j].se + 1]) { union_sets(a[j].se + 1,a[j].se); cnt--; } f[a[j].se] = 1; j++; } i = j; ans = max(ans,cnt); } cout << ans << "\n"; }
#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...