Submission #245389

#	Time	Username	Problem	Language	Result	Execution time	Memory
245389		rama_pang	Fire (JOI20_ho_t5)	C++14	100 / 100	499 ms	73372 KiB

ho_t5

// Solution:
//
// Draw a grid, with rows as time and columns as index. For each original S,
// it must for a parallelogram. Each parallelogram can be decomposed into
// triangles. Each triangle can be stored in 2 Dat Structures that support
// range add and range query, where 1 stores diagonals and the other stores
// the vertical aspect. For the diagonal, we can shift query ranges to the
// left, leaving a rectangular one as well. This can be done using a segment
// tree or 2 fenwick trees, each.

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

class Fenwick {
 private:
  int sz;
  vector<long long> tree;

 public:
  Fenwick() {}
  Fenwick(int sz) : sz(sz) {
    tree.assign(sz, 0);
  }

  void Update(int p, long long x) {
    p += sz / 2;
    for (int i = p; i < sz; i |= i + 1) {
      tree[i] += x;
    }
  }

  long long Query(int p) {
    p += sz / 2;
    long long res = 0;
    for (int i = p + 1; i > 0; i &= i - 1) {
      res += tree[i - 1];
    }
    return res;
  }
};

const int MAXN = 400005;

int N, Q;
int S[MAXN];
int L[MAXN], R[MAXN];

vector<array<int, 3>> query[MAXN];
long long ans[MAXN];

Fenwick start_pref(2 * MAXN);
Fenwick start_const(2 * MAXN);
Fenwick end_pref(2 * MAXN);
Fenwick end_const(2 * MAXN);

vector<array<int, 3>> update[MAXN];

void AddTriangle(int l, int r, int v) {
  if (l > r) return;
  update[0].push_back({l, r, v});
  update[r - l + 1].push_back({l, r, -v});
}

void Update(int t) {
  for (auto u : update[t]) {
    int l, r, v;
    l = u[0], r = u[1], v = u[2];
    start_pref.Update(l, v);
    start_const.Update(l, 1ll * v * (l - 1));
    end_pref.Update(r + 1, -v);
    end_const.Update(r + 1, -1ll * v * r);
  }
}

long long Query(int t, int r) {
  long long start_ = 1ll * (r - t) * start_pref.Query(r - t) - start_const.Query(r - t); // shift to the left
  long long end_ = 1ll * r * end_pref.Query(r) - end_const.Query(r);
  return start_ + end_; 
}

long long Query(int t, int l, int r) {
  return Query(t, r) - Query(t, l - 1);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> Q;
  for (int i = 1; i <= N; i++) {
    cin >> S[i];
    L[i] = - N - 1;
    R[i] = + N + 1;
  }
  vector<int> st;
  for (int i = 1; i <= N; i++) {
    while (!st.empty() && S[st.back()] <= S[i]) {
      st.pop_back();
    }
    if (!st.empty()) {
      L[i] = st.back();
    }
    st.emplace_back(i);
  }
  st.clear();
  for (int i = N; i >= 1; i--) {
    while (!st.empty() && S[st.back()] < S[i]) {
      st.pop_back();
    }
    if (!st.empty()) {
      R[i] = st.back();
    }
    st.emplace_back(i);
  }
  for (int i = 1; i <= N; i++) {
    AddTriangle(L[i] + 1, R[i] - 1, S[i]);
    AddTriangle(L[i] + 1, i - 1, -S[i]);
    AddTriangle(i + 1, R[i] - 1, -S[i]);
  }
  for (int i = 0; i < Q; i++) {
    int t, l, r;
    cin >> t >> l >> r;
    query[t].push_back({l, r, i});
  }
  for (int t = 0; t <= N; t++) {
    Update(t);
    for (auto &q : query[t]) {
      ans[q[2]] = Query(t, q[0], q[1]);
    }
  }
  for (int i = 0; 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