Submission #1037123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037123		NeroZein	Fire (JOI20_ho_t5)	C++17	100 / 100	798 ms	71428 KiB

ho_t5

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 2e5 + 5; 

struct segtree {
  int n;
  vector<long long> seg, lazy;
  segtree() {
    n = N * 3; 
    seg.resize(n * 2);
    lazy.resize(n * 2); 
  }
  void push(int nd, int l, int r) {
    if (!lazy[nd]) {
      return;
    }
    seg[nd] += lazy[nd] * (r - l + 1);
    if (l != r) {
      int mid = (l + r) >> 1;
      int rs = nd + ((mid - l + 1) << 1);
      lazy[nd + 1] += lazy[nd];
      lazy[rs] += lazy[nd]; 
    }
    lazy[nd] = 0; 
  }
  void upd(int nd, int l, int r, int s, int e, int v) {
    push(nd, l, r); 
    if (l >= s && r <= e) {
      lazy[nd] = v; 
      push(nd, l, r); 
      return;
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (mid >= e) {
      upd(nd + 1, l, mid, s, e, v);
      push(rs, mid + 1, r); 
    } else {
      if (mid < s) {
        upd(rs, mid + 1, r, s, e, v); 
        push(nd + 1, l, mid); 
      } else {
        upd(nd + 1, l, mid, s, e, v);
        upd(rs, mid + 1, r, s, e, v); 
      }
    }
    seg[nd] = seg[nd + 1] + seg[rs]; 
  }
  void upd(int s, int e, int v) {
    if (s <= e) {
      s += N, e += N;
      upd(0, 0, n - 1, s, e, v);       
    }
  }
  long long qry(int nd, int l, int r, int s, int e) {
    push(nd, l, r); 
    if (l >= s && r <= e) {
      return seg[nd];
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (mid >= e) {
      return qry(nd + 1, l, mid, s, e);
    } else {
      if (mid < s) {
        return qry(rs, mid + 1, r, s, e);
      } else {
        return qry(nd + 1, l, mid, s, e) + qry(rs, mid + 1, r, s, e);
      }
    }
  }
  long long qry(int s, int e) {
    s += N, e += N;
    return qry(0, 0, n - 1, s, e); 
  }
};

int n, q;
int a[N];
segtree one, two; 
long long ans[N];
int pre[N], nxt[N];
vector<array<int, 3>> qt[N];
vector<array<int, 3>> rev[N];

void triangle(int l, int r, int v) {
  if (l > r) return; 
  one.upd(l, n + n, v); //[-n, 2n] --> [0, 3n] (size = 6N)
  two.upd(r + 1, n, -v); //[2, n] --> [2 + n, 2n] (size = 4N)
  if (r - l + 1 <= n) {
    rev[r - l + 1].push_back({l, r, v});
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  
  stack<int> stk;
  for (int i = 1; i <= n; ++i) {
    while (!stk.empty() && a[stk.top()] <= a[i]) {
      stk.pop();
    }
    if (stk.empty()) {
      pre[i] = -n;
    } else {
      pre[i] = stk.top();
    }
    stk.push(i);
  }
  while (!stk.empty()) {
    stk.pop();
  }
  for (int i = n; i >= 1; --i) {
    while (!stk.empty() && a[stk.top()] < a[i]) {
      stk.pop(); 
    }
    if (stk.empty()) {
      nxt[i] = n + 1; 
    } else {
      nxt[i] = stk.top();
    }
    stk.push(i); 
  }
  
  for (int i = 1; i <= n; ++i) {
    triangle(pre[i] + 1, nxt[i] - 1, a[i]);
    triangle(pre[i] + 1, i - 1, -a[i]);
    triangle(i + 1, nxt[i] - 1, -a[i]); 
  }
  
  for (int i = 1; i <= q; ++i) {
    int t, l, r;
    cin >> t >> l >> r;
    qt[t].push_back({l, r, i});
  }
  
  for (int t = 1; t <= n; ++t) {
    for (auto [l, r, v] : rev[t]) {
      one.upd(l, n + n, -v);
      two.upd(r + 1, n, v); 
    }
    for (auto [l, r, i] : qt[t]) {
      ans[i] = one.qry(l - t, r - t) + two.qry(l, r); 
    }
  }
  
  for (int i = 1; i <= q; ++i) {
    cout << ans[i] << '\n';
  }
  
  return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80