Submission #880697

#TimeUsernameProblemLanguageResultExecution timeMemory
880697MilosMilutinovicFire (JOI20_ho_t5)C++14
100 / 100
340 ms64176 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; vector<int> s(n); for (int i = 0; i < n; i++) { cin >> s[i]; } vector<int> t(q), l(q), r(q); for (int i = 0; i < q; i++) { cin >> t[i] >> l[i] >> r[i]; --l[i]; --r[i]; if (t[i] == n) { --t[i]; } } vector<int> prv(n); vector<int> stk; for (int i = 0; i < n; i++) { while (!stk.empty() && s[i] >= s[stk.back()]) { stk.pop_back(); } prv[i] = (stk.empty() ? -1 : stk.back()); stk.push_back(i); } vector<vector<int>> ch(n); for (int i = 0; i < n; i++) { if (prv[i] != -1) { ch[prv[i]].push_back(i); } } vector<int> to(n); for (int i = n - 1; i >= 0; i--) { to[i] = i; for (int j : ch[i]) { to[i] = max(to[i], to[j]); } } vector<long long> res(q); { vector<long long> pref(n); for (int i = 0; i < n; i++) { if (i > 0) { pref[i] = pref[i - 1]; } pref[i] += s[i]; } for (int i = 0; i < q; i++) { res[i] = pref[r[i]] - (l[i] == 0 ? 0LL : pref[l[i] - 1]); } } vector<vector<array<int, 3>>> seg(n); for (int i = 0; i < n; i++) { for (int j : ch[i]) { seg[to[j]].push_back({s[i] - s[j], j - i, to[j] - i}); } } vector<vector<vector<int>>> qs(n, vector<vector<int>>(2)); for (int i = 0; i < q; i++) { if (l[i] > 0) { qs[l[i] - 1][0].push_back(i); } qs[r[i]][1].push_back(i); } vector<vector<long long>> fenw(4, vector<long long>(n)); auto Modify = [&](int t, int x, long long v) { assert(0 <= x); while (x < n) { fenw[t][x] += v; x |= (x + 1); } }; auto Query = [&](int t, int x) { assert(x < n); long long v = 0; while (x >= 0) { v += fenw[t][x]; x = (x & (x + 1)) - 1; } return v; }; auto QueryRange = [&](int t, int l, int r) { return Query(t, r) - Query(t, l - 1); }; auto AddInc = [&](int L, int R, int v) { Modify(0, L, +v); Modify(1, L, (L - 1) * 1LL * v); Modify(0, R, -v); Modify(1, R, -R * 1LL * v); }; auto Ins = [&](int i, int j) { AddInc(j - i, n - 1, s[i] - s[j]); Modify(2, i, s[i] - s[j]); Modify(3, i, i * 1LL * (s[i] - s[j])); }; auto Rem = [&](int i, int j) { AddInc(j - i, n - 1, s[j] - s[i]); Modify(2, i, s[j] - s[i]); Modify(3, i, i * 1LL * (s[j] - s[i])); }; auto Solve = [&](int i, int k) { long long ret = 0; ret += Query(0, k) * k; ret -= Query(1, k); int low = 0, high = (int) stk.size() - 1, pos = -1; while (low <= high) { int mid = low + high >> 1; if (i - stk[mid] < k) { pos = mid; high = mid - 1; } else { low = mid + 1; } } if (pos != -1) { ret -= (k - i) * QueryRange(2, stk[pos], i); ret -= QueryRange(3, stk[pos], i); } return ret; }; stk.clear(); for (int i = 0; i < n; i++) { while (!stk.empty() && s[stk.back()] <= s[i]) { if (stk.size() > 1) { Rem(stk[stk.size() - 2], stk.back()); } stk.pop_back(); } if (!stk.empty()) { Ins(stk.back(), i); } stk.push_back(i); for (int j : qs[i][0]) { res[j] -= Solve(i, t[j]); } for (int j : qs[i][1]) { res[j] += Solve(i, t[j]); } for (auto& p : seg[i]) { AddInc(p[1], p[2], p[0]); } } for (int i = 0; i < q; i++) { cout << res[i] << '\n'; } return 0; }

Compilation message (stderr)

ho_t5.cpp: In lambda function:
ho_t5.cpp:112:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |       int mid = low + high >> 1;
      |                 ~~~~^~~~~~
#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...