Submission #1012928

#TimeUsernameProblemLanguageResultExecution timeMemory
1012928EJIC_B_KEDAXFire (JOI20_ho_t5)C++17
100 / 100
237 ms65608 KiB
#include <bits/stdc++.h> #include <immintrin.h> using namespace std; using ll = long long; using ld = long double; #define x first #define y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() mt19937 mt(123); void solve(); void init(); int32_t main() { #ifndef LOCAL cin.tie(nullptr)->sync_with_stdio(false); #endif cout << fixed << setprecision(30); init(); int t = 1; // cin >> t; while (t--) { solve(); } } struct segment_tree { vector<ll> st; int sz; segment_tree() = default; segment_tree(vector<int> a) { sz = 1; while (sz < a.size()) { sz <<= 1; } st.resize(2 * sz, 0); for (int i = 0; i < a.size(); i++) { st[sz + i] = a[i]; } for (int i = sz - 1; i > 0; i--) { st[i] = st[2 * i] + st[2 * i + 1]; } } void add(int i, ll x) { i += sz; while (i) { st[i] += x; i >>= 1; } } ll get(int l, int r) { l += sz; r += sz; ll res = 0; while (l <= r) { if (l & 1) { res += st[l++]; } if (~r & 1) { res += st[r--]; } l >>= 1; r >>= 1; } return res; } }; struct mseg_tree { segment_tree def, step; int now_step; mseg_tree() = default; mseg_tree(int n) { now_step = 0; def = segment_tree(vector<int>(n, 0)); step = segment_tree(vector<int>(n, 0)); } void add_def(int i, int x) { def.add(i, x); } void add_step(int i, int x) { step.add(i, x); def.add(i, -1ll * x * now_step); } void next_step() { now_step++; } void set_step(int new_step) { now_step = new_step; } ll get(int l, int r) { return def.get(l, r) + now_step * step.get(l, r); } }; struct sparse_max { using Type = pair<int, int>; vector<vector<Type>> sp; vector<int> p; sparse_max(const vector<Type>& a) { int n = a.size(), lg = 1; while ((1 << lg) < n) { lg++; } sp.resize(lg, vector<Type>(n)); for (int i = 0; i < n; i++) { sp[0][i] = a[i]; } for (int l = 1; l < lg; l++) { for (int i = 0; i <= n - (1 << l); i++) { sp[l][i] = max(sp[l - 1][i], sp[l - 1][i + (1 << (l - 1))]); } } int nw = 0; p.resize(n + 1, 0); for (int i = 1; i <= n; i++) { if ((1 << nw) * 2 < i) { nw++; } p[i] = nw; } } Type get(int l, int r) { int lev = p[r - l + 1]; return max(sp[lev][l], sp[lev][r - (1 << lev) + 1]); } }; struct sparse_min { using Type = pair<int, int>; vector<vector<Type>> sp; vector<int> p; sparse_min(const vector<Type>& a) { int n = a.size(), lg = 1; while ((1 << lg) < n) { lg++; } sp.resize(lg, vector<Type>(n)); for (int i = 0; i < n; i++) { sp[0][i] = a[i]; } for (int l = 1; l < lg; l++) { for (int i = 0; i <= n - (1 << l); i++) { sp[l][i] = min(sp[l - 1][i], sp[l - 1][i + (1 << (l - 1))]); } } int nw = 0; p.resize(n + 1, 0); for (int i = 1; i <= n; i++) { if ((1 << nw) * 2 < i) { nw++; } p[i] = nw; } } Type get(int l, int r) { int lev = p[r - l + 1]; return min(sp[lev][l], sp[lev][r - (1 << lev) + 1]); } }; void init() {} void solve() { int n, q; cin >> n >> q; vector<int> a(n), nxt(n), prv(n); for (int i = 0; i < n; i++) { cin >> a[i]; } // assert(n == 1); mseg_tree st(n); for (int i = 0; i < n; i++) { st.add_step(i, a[i]); } vector<pair<int, int>> stack(1, {INT32_MAX, n}); for (int i = n - 1; i >= 0; i--) { while (a[i] >= stack.back().x) { stack.pop_back(); } nxt[i] = stack.back().y; stack.emplace_back(a[i], i); } stack.clear(); stack.emplace_back(INT32_MAX, -1); for (int i = 0; i < n; i++) { while (a[i] > stack.back().x) { stack.pop_back(); } prv[i] = stack.back().y; stack.emplace_back(a[i], i); } vector<pair<int, int>> fsp(n); for (int i = 0; i < n; i++) { fsp[i] = {a[i], -i}; } sparse_max sp(fsp); vector<pair<int, pair<int, int>>> ev; vector<pair<int, int>> qu; vector<pair<int, int>> seg(q); vector<ll> ans(q); for (int i = 0; i < q; i++) { int t, l, r; cin >> t >> l >> r; l--; r--; qu.emplace_back(t, i); seg[i] = {l, r}; } for (int i = 0; i < n; i++) { ev.emplace_back(nxt[i] - i, make_pair(i, -a[i])); if (prv[i] != -1) { ev.emplace_back(i - prv[i], make_pair(i, -a[i])); ev.emplace_back(nxt[i] - prv[i], make_pair(i, a[i])); } } sort(all(ev)); sort(all(qu)); int ptrev = 0, ptrqu = 0; for (int t = 0; t <= n; t++) { while (ptrev < ev.size() && ev[ptrev].x == t) { st.add_step(ev[ptrev].y.x, ev[ptrev].y.y); ptrev++; } st.next_step(); while (ptrqu < qu.size() && qu[ptrqu].x == t) { int i = qu[ptrqu++].y; auto [l, r] = seg[i]; r++; ll lans = 0, rans = 0; { auto [mx, mxi] = sp.get(max(0, l - t), l); mxi *= -1; lans = st.get(mxi + 1, n - 1); int lst = min({mxi + t, nxt[mxi] - 1}); lans += 1ll * (lst - l + 1) * mx; } if (r < n) { auto [mx, mxi] = sp.get(max(0, r - t), r); mxi *= -1; rans = st.get(mxi + 1, n - 1); int lst = min(mxi + t, nxt[mxi] - 1); rans += 1ll * (lst - r + 1) * mx; } ans[i] = lans - rans; } } for (ll i : ans) { cout << i << '\n'; } }

Compilation message (stderr)

ho_t5.cpp: In constructor 'segment_tree::segment_tree(std::vector<int>)':
ho_t5.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while (sz < a.size()) {
      |                ~~~^~~~~~~~~~
ho_t5.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0; i < a.size(); i++) {
      |                         ~~^~~~~~~~~~
ho_t5.cpp: In function 'void solve()':
ho_t5.cpp:222:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |         while (ptrev < ev.size() && ev[ptrev].x == t) {
      |                ~~~~~~^~~~~~~~~~~
ho_t5.cpp:227:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  227 |         while (ptrqu < qu.size() && qu[ptrqu].x == t) {
      |                ~~~~~~^~~~~~~~~~~
#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...