oj.uz

Submission #245389

# Submission time Handle Problem Language Result Execution time Memory
245389 2020-07-06T09:02:15 Z rama_pang Fire (JOI20_ho_t5) C++14
100 / 100
 499 ms 73372 KB 
// 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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 44160 KB Output is correct
2 Correct 27 ms 44288 KB Output is correct
3 Correct 27 ms 44288 KB Output is correct
4 Correct 31 ms 44288 KB Output is correct
5 Correct 32 ms 44280 KB Output is correct
6 Correct 28 ms 44280 KB Output is correct
7 Correct 28 ms 44288 KB Output is correct
8 Correct 27 ms 44280 KB Output is correct
9 Correct 28 ms 44336 KB Output is correct
10 Correct 27 ms 44288 KB Output is correct
11 Correct 32 ms 44280 KB Output is correct
12 Correct 27 ms 44288 KB Output is correct
13 Correct 28 ms 44288 KB Output is correct
14 Correct 30 ms 44276 KB Output is correct
15 Correct 28 ms 44288 KB Output is correct
16 Correct 28 ms 44280 KB Output is correct
17 Correct 27 ms 44288 KB Output is correct
18 Correct 29 ms 44280 KB Output is correct
19 Correct 29 ms 44416 KB Output is correct
20 Correct 28 ms 44288 KB Output is correct
21 Correct 28 ms 44280 KB Output is correct
22 Correct 27 ms 44280 KB Output is correct
23 Correct 29 ms 44288 KB Output is correct
24 Correct 28 ms 44288 KB Output is correct
25 Correct 27 ms 44288 KB Output is correct
26 Correct 28 ms 44288 KB Output is correct
27 Correct 27 ms 44288 KB Output is correct
28 Correct 29 ms 44260 KB Output is correct
29 Correct 28 ms 44288 KB Output is correct
30 Correct 27 ms 44284 KB Output is correct
31 Correct 28 ms 44284 KB Output is correct
32 Correct 27 ms 44288 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 44160 KB Output is correct
2 Correct 372 ms 71964 KB Output is correct
3 Correct 371 ms 71836 KB Output is correct
4 Correct 385 ms 72096 KB Output is correct
5 Correct 402 ms 73244 KB Output is correct
6 Correct 402 ms 71708 KB Output is correct
7 Correct 370 ms 72092 KB Output is correct
8 Correct 413 ms 73372 KB Output is correct
9 Correct 396 ms 72580 KB Output is correct
10 Correct 386 ms 71836 KB Output is correct
11 Correct 391 ms 72860 KB Output is correct
12 Correct 378 ms 71836 KB Output is correct
13 Correct 382 ms 72732 KB Output is correct
14 Correct 373 ms 72860 KB Output is correct
15 Correct 384 ms 72860 KB Output is correct
16 Correct 395 ms 71964 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 44160 KB Output is correct
2 Correct 462 ms 70252 KB Output is correct
3 Correct 464 ms 69508 KB Output is correct
4 Correct 485 ms 71008 KB Output is correct
5 Correct 408 ms 69660 KB Output is correct
6 Correct 430 ms 70044 KB Output is correct
7 Correct 443 ms 69892 KB Output is correct
8 Correct 458 ms 69916 KB Output is correct
9 Correct 433 ms 69788 KB Output is correct
10 Correct 458 ms 69532 KB Output is correct
11 Correct 490 ms 70940 KB Output is correct
12 Correct 446 ms 70432 KB Output is correct
13 Correct 484 ms 70460 KB Output is correct
14 Correct 447 ms 69660 KB Output is correct
15 Correct 458 ms 70176 KB Output is correct
16 Correct 418 ms 69948 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 68188 KB Output is correct
2 Correct 427 ms 67932 KB Output is correct
3 Correct 429 ms 68492 KB Output is correct
4 Correct 423 ms 68316 KB Output is correct
5 Correct 382 ms 68060 KB Output is correct
6 Correct 406 ms 68316 KB Output is correct
7 Correct 385 ms 68296 KB Output is correct
8 Correct 405 ms 68440 KB Output is correct
9 Correct 419 ms 68060 KB Output is correct
10 Correct 402 ms 68292 KB Output is correct
11 Correct 420 ms 68444 KB Output is correct
12 Correct 394 ms 68444 KB Output is correct
13 Correct 392 ms 68188 KB Output is correct
14 Correct 422 ms 68192 KB Output is correct

Subtask #5
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 44160 KB Output is correct
2 Correct 27 ms 44288 KB Output is correct
3 Correct 27 ms 44288 KB Output is correct
4 Correct 31 ms 44288 KB Output is correct
5 Correct 32 ms 44280 KB Output is correct
6 Correct 28 ms 44280 KB Output is correct
7 Correct 28 ms 44288 KB Output is correct
8 Correct 27 ms 44280 KB Output is correct
9 Correct 28 ms 44336 KB Output is correct
10 Correct 27 ms 44288 KB Output is correct
11 Correct 32 ms 44280 KB Output is correct
12 Correct 27 ms 44288 KB Output is correct
13 Correct 28 ms 44288 KB Output is correct
14 Correct 30 ms 44276 KB Output is correct
15 Correct 28 ms 44288 KB Output is correct
16 Correct 28 ms 44280 KB Output is correct
17 Correct 27 ms 44288 KB Output is correct
18 Correct 29 ms 44280 KB Output is correct
19 Correct 29 ms 44416 KB Output is correct
20 Correct 28 ms 44288 KB Output is correct
21 Correct 28 ms 44280 KB Output is correct
22 Correct 27 ms 44280 KB Output is correct
23 Correct 29 ms 44288 KB Output is correct
24 Correct 28 ms 44288 KB Output is correct
25 Correct 27 ms 44288 KB Output is correct
26 Correct 28 ms 44288 KB Output is correct
27 Correct 27 ms 44288 KB Output is correct
28 Correct 29 ms 44260 KB Output is correct
29 Correct 28 ms 44288 KB Output is correct
30 Correct 27 ms 44284 KB Output is correct
31 Correct 28 ms 44284 KB Output is correct
32 Correct 27 ms 44288 KB Output is correct
33 Correct 499 ms 70944 KB Output is correct
34 Correct 465 ms 71324 KB Output is correct
35 Correct 439 ms 71020 KB Output is correct
36 Correct 430 ms 70816 KB Output is correct
37 Correct 435 ms 70724 KB Output is correct
38 Correct 495 ms 71068 KB Output is correct
39 Correct 423 ms 70816 KB Output is correct
40 Correct 425 ms 70868 KB Output is correct
41 Correct 433 ms 71580 KB Output is correct
42 Correct 444 ms 70940 KB Output is correct
43 Correct 391 ms 71080 KB Output is correct
44 Correct 452 ms 71452 KB Output is correct
45 Correct 399 ms 70300 KB Output is correct
46 Correct 399 ms 71324 KB Output is correct
47 Correct 379 ms 70044 KB Output is correct
48 Correct 430 ms 70044 KB Output is correct
49 Correct 446 ms 70684 KB Output is correct
50 Correct 467 ms 71580 KB Output is correct
51 Correct 457 ms 71580 KB Output is correct
52 Correct 414 ms 70740 KB Output is correct
53 Correct 384 ms 70684 KB Output is correct
54 Correct 405 ms 70088 KB Output is correct
55 Correct 403 ms 70300 KB Output is correct
56 Correct 437 ms 70428 KB Output is correct
57 Correct 399 ms 70172 KB Output is correct
58 Correct 410 ms 71336 KB Output is correct
59 Correct 372 ms 71964 KB Output is correct
60 Correct 371 ms 71836 KB Output is correct
61 Correct 385 ms 72096 KB Output is correct
62 Correct 402 ms 73244 KB Output is correct
63 Correct 402 ms 71708 KB Output is correct
64 Correct 370 ms 72092 KB Output is correct
65 Correct 413 ms 73372 KB Output is correct
66 Correct 396 ms 72580 KB Output is correct
67 Correct 386 ms 71836 KB Output is correct
68 Correct 391 ms 72860 KB Output is correct
69 Correct 378 ms 71836 KB Output is correct
70 Correct 382 ms 72732 KB Output is correct
71 Correct 373 ms 72860 KB Output is correct
72 Correct 384 ms 72860 KB Output is correct
73 Correct 395 ms 71964 KB Output is correct
74 Correct 462 ms 70252 KB Output is correct
75 Correct 464 ms 69508 KB Output is correct
76 Correct 485 ms 71008 KB Output is correct
77 Correct 408 ms 69660 KB Output is correct
78 Correct 430 ms 70044 KB Output is correct
79 Correct 443 ms 69892 KB Output is correct
80 Correct 458 ms 69916 KB Output is correct
81 Correct 433 ms 69788 KB Output is correct
82 Correct 458 ms 69532 KB Output is correct
83 Correct 490 ms 70940 KB Output is correct
84 Correct 446 ms 70432 KB Output is correct
85 Correct 484 ms 70460 KB Output is correct
86 Correct 447 ms 69660 KB Output is correct
87 Correct 458 ms 70176 KB Output is correct
88 Correct 418 ms 69948 KB Output is correct
89 Correct 413 ms 68188 KB Output is correct
90 Correct 427 ms 67932 KB Output is correct
91 Correct 429 ms 68492 KB Output is correct
92 Correct 423 ms 68316 KB Output is correct
93 Correct 382 ms 68060 KB Output is correct
94 Correct 406 ms 68316 KB Output is correct
95 Correct 385 ms 68296 KB Output is correct
96 Correct 405 ms 68440 KB Output is correct
97 Correct 419 ms 68060 KB Output is correct
98 Correct 402 ms 68292 KB Output is correct
99 Correct 420 ms 68444 KB Output is correct
100 Correct 394 ms 68444 KB Output is correct
101 Correct 392 ms 68188 KB Output is correct
102 Correct 422 ms 68192 KB Output is correct