Submission #888090

#TimeUsernameProblemLanguageResultExecution timeMemory
888090votranngocvyPo (COCI21_po)C++14
70 / 70
32 ms10576 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll,int> #define fi first #define se second #define mp make_pair const int N = 1e5 + 5; const int inf = 0x3f3f3f3f; int n; ll a[N],ans; pii st[4 * N]; pii merge(pii a,pii b) { if (a.fi <= b.fi) return a; else return b; } void build(int id,int l,int r) { if (l == r) { st[id] = mp(a[l],l); return; } int mid = (l + r) / 2; build(id * 2,l,mid); build(id * 2 + 1,mid + 1,r); st[id] = merge(st[id * 2],st[id * 2 + 1]); } pii get(int id,int l,int r,int u,int v) { if (v < l || r < u) return mp(inf,-1); if (u <= l && r <= v) return st[id]; int mid = (l + r) / 2; return merge(get(id * 2,l,mid,u,v),get(id * 2 + 1,mid + 1,r,u,v)); } void calc(int l,int r,int val) { if (l > r) return; pii tmp = get(1,1,n,l,r); ans += ((tmp.fi - val) != 0); calc(l,tmp.se - 1,tmp.fi); calc(tmp.se + 1,r,tmp.fi); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; build(1,1,n); calc(1,n,0); cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...