Submission #958559

#TimeUsernameProblemLanguageResultExecution timeMemory
958559peterandvoiFire (JOI20_ho_t5)C++17
100 / 100
271 ms30292 KiB
#include <bits/stdc++.h> using namespace std; #ifdef ngu #include "debug.h" #else #define debug(...) 42 #endif #define int long long const int N = (int) 2e5 + 5; int n, q; int a[N], res[N]; vector<pair<int, int>> Q[N]; struct fenwick { int n; vector<int> s; fenwick(int n): n(n) { s.resize(n); } void upd(int i, int x) { for (; i <= n; i += i & -i) { s[i - 1] += x; } } int get(int i) { int res = 0; for (; i; i -= i & -i) { res += s[i - 1]; } return res; } }; signed main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef ngu freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); #endif cin >> n >> q; for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i <= q; ++i) { int t, l, r; cin >> t >> l >> r; Q[r].emplace_back(t, i); Q[l - 1].emplace_back(t, -i); } fenwick ft1(n + 1), ft2(n + 1); auto upd = [&](int i, int v) { i++; ft1.upd(i, v); ft2.upd(i, -v * (i - 1)); }; auto get = [&](int i) { i++; return ft1.get(i) * i + ft2.get(i); }; vector<int> st, pref; st.emplace_back(-n); pref.emplace_back(0); for (int i = 1; i <= n; ++i) { while (st.size() && st.back() > 0 && a[st.back()] <= a[i]) { upd(i - st.back(), -a[st.back()]); upd(i - st.end()[-2], a[st.back()]); st.pop_back(); pref.pop_back(); } upd(0, a[i]); upd(i - st.back(), -a[i]); pref.emplace_back(pref.back() + (i - st.back()) * a[i]); st.emplace_back(i); for (auto [t, id] : Q[i]) { int val = get(t); int p = lower_bound(st.begin(), st.end(), i - t) - st.begin(); val -= (st[p] + t - i) * a[st[p]] + pref.back() - pref[p]; if (id > 0) { res[id] += val; } else { res[-id] -= val; } } } for (int i = 1; i <= q; ++i) { cout << res[i] << "\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...
#Verdict Execution timeMemoryGrader output
Fetching results...