Submission #533250

#TimeUsernameProblemLanguageResultExecution timeMemory
533250koioi.org-koosagaDungeon 3 (JOI21_ho_t5)C++17
11 / 100
4098 ms25108 KiB
#include <bits/stdc++.h> #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() using namespace std; typedef long long lint; typedef pair<lint, lint> pi; const int mod = 1e9 + 7; const int MAXN = 200050; const int MAXT = 530000; struct intv{ int s, e; lint x; }; struct query{ int s, e; lint x; int idx; }; struct bit{ lint tree[MAXN]; void add(int x, lint v){ for(int i = x; i < MAXN; i += i & -i) tree[i] += v; } lint query(int x){ lint ret = 0; for(int i = x; i; i -= i & -i) ret += tree[i]; return ret; } lint query(int s, int e){ return query(e) - query(s - 1); } }bit1, bit2; struct seg{ int tree[MAXT], lim; void init(int n){ for(lim = 1; lim <= n; lim <<= 1); } void upd(int x, int v){ for(int i = x+lim; i; i >>= 1){ tree[i] = max(tree[i], v); } } int query(int s, int e){ s += lim; e += lim; int ret = 0; while(s < e){ if(s%2 == 1) ret = max(ret, tree[s++]); if(e%2 == 0) ret = max(ret, tree[e--]); s >>= 1; e >>= 1; } if(s == e) ret = max(ret, tree[s]); return ret; } }seg; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<lint> a(n + 1), b(n); seg.init(n); for(int i = 1; i <= n; i++){ cin >> a[i], a[i] += a[i - 1]; seg.upd(i, a[i] - a[i-1]); } for(int i = 0; i < n; i++) cin >> b[i]; vector<intv> v; { vector<int> stk; vector<int> l(n), r(n); for(int i = 0; i < n; i++){ while(sz(stk) && b[stk.back()] > b[i]){ stk.pop_back(); } l[i] = (sz(stk) ? stk.back() : -1); stk.push_back(i); } stk.clear(); for(int i = n-1; i >= 0; i--){ while(sz(stk) && b[stk.back()] >= b[i]){ stk.pop_back(); } r[i] = (sz(stk) ? stk.back() : n); stk.push_back(i); } stk.clear(); for(int i = 0; i < n; i++){ lint lo = 0; if(l[i] >= 0) lo = max(lo, b[l[i]]); if(r[i] < n) lo = max(lo, b[r[i]]); v.push_back({l[i] + 2, r[i], b[i] - lo}); } } vector<lint> ans(m); vector<query> qry; for(int i = 0; i < m; i++){ int s, e; lint x; cin >> s >> e >> x; e--; if(seg.query(s, e) > x){ ans[i] = -1; continue; } qry.push_back({s, e, x, i}); } sort(all(v), [&](const intv &a, const intv &b){ return a.s < b.s; }); sort(all(qry), [&](const query &a, const query &b){ return a.s < b.s; }); int pv = 0, pq = 0; for(int i = 1; i <= n; i++){ while(pv < sz(v) && v[pv].s == i){ bit1.add(v[pv].e, v[pv].x); bit2.add(v[pv].e, v[pv].x * a[v[pv].e]); pv++; } while(pq < sz(qry) && qry[pq].s == i){ auto Q = qry[pq++]; ans[Q.idx] += (a[Q.e] - a[Q.s - 1]) * bit1.query(Q.e, n); ans[Q.idx] += bit2.query(Q.s, Q.e - 1); ans[Q.idx] -= a[Q.s - 1] * bit1.query(Q.s, Q.e - 1); } } for(auto &x : qry){ for(auto &j : v){ if(j.s > x.s){ if(j.e > x.e) ans[x.idx] += j.x * max(0ll, a[x.e] - a[j.s - 2] - x.x); else ans[x.idx] += j.x * max(0ll, a[j.e] - a[j.s - 2] - x.x); } } } for(auto &a : ans) cout << a << "\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...