Submission #946949

#TimeUsernameProblemLanguageResultExecution timeMemory
946949phoenix0423Constellation 3 (JOI20_constellation3)C++17
100 / 100
158 ms32976 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define fastio ios::sync_with_stdio(false), cin.tie(0) #define pb push_back #define eb emplace_back #define f first #define s second #define int long long #define lowbit(x) x&-x const int maxn = 2e5 + 5; int BIT[maxn]; int l[maxn], r[maxn], h[maxn]; vector<int> mg[maxn]; vector<pll> star[maxn]; int n; void upd(int pos, int val){ while(pos < maxn){ BIT[pos] += val; pos += lowbit(pos); } } int qry(int pos){ if(pos < 0) return 0; int ret = 0; while(pos){ ret += BIT[pos]; pos -= lowbit(pos); } return ret; } int rootl(int x){ return l[x] == x ? l[x] : l[x] = rootl(l[x]);} int rootr(int x){ return r[x] == x ? r[x] : r[x] = rootr(r[x]);} void merge(int a, int b){ l[b] = rootl(a); r[a] = rootr(b); } signed main(void){ fastio; cin>>n; for(int i = 1; i <= n; i++) l[i] = r[i] = i; for(int i = 1; i <= n; i++){ cin>>h[i]; mg[h[i]].pb(i); } int m; cin>>m; for(int i = 0; i < m; i++){ int a, b, w; cin>>a>>b>>w; star[b].eb(a, w); } int ans = 0; for(int i = 1; i <= n; i++){ for(auto [x, w] : star[i]){ l[x] = rootl(l[x]), r[x] = rootr(r[x]); int val = qry(x); if(val > w) ans += w; else ans += val, upd(l[x], w - val), upd(r[x] + 1, val - w); } for(auto x : mg[i]){ if(x > 1 && h[x - 1] <= h[x]) merge(x - 1, x); if(x < n && h[x + 1] <= h[x]) merge(x, x + 1); } } cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...