Submission #361688

#TimeUsernameProblemLanguageResultExecution timeMemory
361688daringtriflesGlobal Warming (NOI13_gw)C++17
13 / 40
1093 ms64780 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define ll int #define pll pair<ll, ll> #define FOR(i, a, b) for (signed ll i = (signed ll)(a); i < (signed ll)(b); i++) #define NEGFOR(i, a, b) for (ll i = (a); i > (b); i--) #define vll vector<ll> #define sll set<ll> #define ld long double #define inf 10000000000 #define mll multiset<ll> #define vpll vector<pll> #define nn << "\n" #define ss << " " //10^8 operations per second //greatest int is 2,147,483,647 //greates long long is 9.22337204e18 //ALL FUNCTIONS SHOULD BE LL!!!! vll parent(1000005),sz(1000005); void make_set(ll v) { parent[v] = v; sz[v] = 1; } ll find_set(ll v) { if (v == parent[v]) return v; return parent[v] = find_set(parent[v]); } void unite(ll a, ll b) { a = find_set(a); b = find_set(b); if (a != b) { if (sz[a] < sz[b]) swap(a, b); parent[b] = a; sz[a] += sz[b]; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll n; cin>>n; vpll v(n); FOR(i,0,n){ cin>>v[i].first; v[i].second=i; } sort(v.rbegin(),v.rend()); map<ll,bool> risen; ll curr=0,ans=-1; FOR(i,0,n){ make_set(v[i].second); curr++; risen[v[i].second]=1; if (risen[v[i].second-1]){ unite(v[i].second-1,v[i].second); --curr; } if (risen[v[i].second+1]){ unite(v[i].second+1,v[i].second);--curr; } if (i+1<n&&v[i+1].second==v[i].second) continue; ans=max(ans,curr); } cout<<ans; }
#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...