제출 #983807

#제출 시각아이디문제언어결과실행 시간메모리
983807vjudge1Growing Vegetables is Fun 4 (JOI21_ho_t1)C++17
100 / 100
144 ms8064 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define str string struct SegTree { int size = 1; vector<int> adds; SegTree (int n){ while(size < n) size <<= 1; adds.resize(size << 1); } void add(int l, int r, int v, int x, int lx, int rx){ if(l <= lx and rx <= r){ adds[x] += v; return; } if(rx <= l or r <= lx) return; int m = (lx + rx) >> 1; add(l, r, v, (x << 1) + 1, lx, m); add(l, r, v, (x << 1) + 2, m, rx); } void add(int l, int r, int x){ add(l, r, x, 0, 0, size); } int get(int n, int x, int lx, int rx){ if(lx + 1 == rx) return adds[x]; int mid = (lx + rx) >> 1; if(n < mid) return get(n, (x << 1) + 1, lx, mid) + adds[x]; else return get(n, (x << 1) + 2, mid, rx) + adds[x]; } int get(int i){ return get(i, 0, 0, size); } }; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int a[n]; for(int i = 0; i < n; i ++) cin >> a[i]; int left = 0, right = n - 1; int ans = 0; SegTree s(n); for(int i = 0; i < n; i ++) s.add(i, i + 1, a[i]); while(left < right){ while(left + 1 < n and s.get(left) < s.get(left + 1)) left ++; while(right - 1 >= 0 and s.get(right - 1) > s.get(right)) right --; if(left < right){ if(left + 1 == right and s.get(left) == s.get(right)){ ans ++; break; } int x = s.get(left) - s.get(left + 1) + 1, y = s.get(right) - s.get(right - 1) + 1; if(x <= y) ans += x, s.add(left + 1, right, x); else ans += y, s.add(left + 1, right, y); } else break; } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...