oj.uz

Submission #1042472

# Submission time Handle Problem Language Result Execution time Memory
1042472 2024-08-03T05:08:30 Z juicy Fire (JOI20_ho_t5) C++17
1 / 100
 76 ms 51392 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n, q;
int a[N], lt[N];
long long res[N];
vector<array<int, 3>> events[N], Queries[N];

struct Fenwick {
  long long s[2 * N];

  void upd(int i, long long x) {
    for (; i <= 2 * n; i += i & -i) {
      s[i] += x;
    }
  }

  void upd(int l, int r, long long x) {
    upd(l, x);
    upd(r + 1, -x);
  }

  long long qry(int i) {
    long long res = 0;
    for (; i; i -= i & -i) {
      res += s[i];
    }
    return res;
  }

  long long qry(int l, int r) {
    return qry(r) - qry(l - 1);
  }
} ft[5];

void upd(int l, int r, int x) {
  int len = r - l + 1;
  ft[0].upd(r + 1, (long long) x * len);
  ft[0].upd(l, r, (long long) -l * x);
  ft[1].upd(r + 1, -x);
  ft[2].upd(l, r, x);
  ft[3].upd(l, -x);
  ft[4].upd(l, (long long) x * l);
}

long long qry(int i, int t) {
  i += n;
  long long x = ft[2].qry(i) + ft[3].qry(i - t + 1, i);
  return ft[0].qry(i) + ft[1].qry(i) * t + x * (i + 1 - t) + ft[4].qry(i - t + 1, i);
}

void add(int l, int r, int h, int x) {
  l += n, r += n;
  events[0].push_back({l, r, x});
  events[h].push_back({l, r, -x});
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= q; ++i) {
    int l, r, t; cin >> t >> l >> r;
    Queries[t].push_back({l, r, i});
  }
  vector<int> st = {-n};
  for (int i = 1; i <= n; ++i) {
    while (st.size() > 1 && a[st.back()] <= a[i]) {
      st.pop_back();
    }
    lt[i] = st.back();
    st.push_back(i);
  }
  st.clear();
  st.push_back(n + 1);
  for (int i = n; i > 0; --i) {
    while (st.size() > 1 && a[st.back()] < a[i]) {
      st.pop_back();
    }
    int r = st.back();
    if (lt[i] + 1 < i) {
      add(lt[i] + 1, i - 1, i - lt[i] - 1, -a[i]);
    }
    if (i < r - 1) {
      add(i + 1, r - 1, r - i - 1, -a[i]);
    }
    add(lt[i] + 1, r - 1, r - lt[i] - 1, a[i]);
    st.push_back(i);
  }
  for (int t = 0; t <= n; ++t) {
    for (auto [l, r, x] : events[t]) {
      upd(l, r, x);
    }
    for (auto [l, r, id] : Queries[t]) {
      res[id] = qry(r, t) - qry(l - 1, t);
    }
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20828 KB Output is correct
2 Correct 2 ms 20828 KB Output is correct
3 Correct 2 ms 20828 KB Output is correct
4 Correct 2 ms 20828 KB Output is correct
5 Correct 2 ms 20828 KB Output is correct
6 Correct 2 ms 20828 KB Output is correct
7 Correct 2 ms 20828 KB Output is correct
8 Correct 3 ms 20936 KB Output is correct
9 Correct 3 ms 20828 KB Output is correct
10 Correct 3 ms 20828 KB Output is correct
11 Correct 2 ms 20824 KB Output is correct
12 Correct 3 ms 20824 KB Output is correct
13 Correct 3 ms 20828 KB Output is correct
14 Correct 2 ms 21020 KB Output is correct
15 Correct 2 ms 20828 KB Output is correct
16 Correct 2 ms 20828 KB Output is correct
17 Correct 3 ms 20828 KB Output is correct
18 Correct 3 ms 20828 KB Output is correct
19 Correct 2 ms 20828 KB Output is correct
20 Correct 3 ms 20828 KB Output is correct
21 Correct 3 ms 20828 KB Output is correct
22 Correct 2 ms 20828 KB Output is correct
23 Correct 3 ms 20828 KB Output is correct
24 Correct 2 ms 20828 KB Output is correct
25 Correct 3 ms 21024 KB Output is correct
26 Correct 3 ms 21080 KB Output is correct
27 Correct 2 ms 20828 KB Output is correct
28 Correct 3 ms 20828 KB Output is correct
29 Correct 2 ms 20828 KB Output is correct
30 Correct 3 ms 20828 KB Output is correct
31 Correct 2 ms 20964 KB Output is correct
32 Correct 2 ms 20824 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20828 KB Output is correct
2 Runtime error 76 ms 51392 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20828 KB Output is correct
2 Runtime error 69 ms 43860 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 40976 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20828 KB Output is correct
2 Correct 2 ms 20828 KB Output is correct
3 Correct 2 ms 20828 KB Output is correct
4 Correct 2 ms 20828 KB Output is correct
5 Correct 2 ms 20828 KB Output is correct
6 Correct 2 ms 20828 KB Output is correct
7 Correct 2 ms 20828 KB Output is correct
8 Correct 3 ms 20936 KB Output is correct
9 Correct 3 ms 20828 KB Output is correct
10 Correct 3 ms 20828 KB Output is correct
11 Correct 2 ms 20824 KB Output is correct
12 Correct 3 ms 20824 KB Output is correct
13 Correct 3 ms 20828 KB Output is correct
14 Correct 2 ms 21020 KB Output is correct
15 Correct 2 ms 20828 KB Output is correct
16 Correct 2 ms 20828 KB Output is correct
17 Correct 3 ms 20828 KB Output is correct
18 Correct 3 ms 20828 KB Output is correct
19 Correct 2 ms 20828 KB Output is correct
20 Correct 3 ms 20828 KB Output is correct
21 Correct 3 ms 20828 KB Output is correct
22 Correct 2 ms 20828 KB Output is correct
23 Correct 3 ms 20828 KB Output is correct
24 Correct 2 ms 20828 KB Output is correct
25 Correct 3 ms 21024 KB Output is correct
26 Correct 3 ms 21080 KB Output is correct
27 Correct 2 ms 20828 KB Output is correct
28 Correct 3 ms 20828 KB Output is correct
29 Correct 2 ms 20828 KB Output is correct
30 Correct 3 ms 20828 KB Output is correct
31 Correct 2 ms 20964 KB Output is correct
32 Correct 2 ms 20824 KB Output is correct
33 Runtime error 76 ms 51392 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -