Submission #1302079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302079		lmquan	Fire (JOI20_ho_t5)	C++20	100 / 100	431 ms	49508 KiB

ho_t5

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

typedef long long ll;

struct FenwickTree {
  int n;
  vector<pair<ll, ll>> bit;

  FenwickTree() {}
  FenwickTree(int _n) : n(_n) {
    bit.resize(n + 1, {0, 0});
  }

  void Update(int pos, pair<ll, ll> val) {
    for (int i = pos; i <= n; i += i & (-i)) {
      bit[i].first += val.first;
      bit[i].second += val.second;
    }
  }

  pair<ll, ll> PrefixSum(int pos) {
    pair<ll, ll> sum = {0, 0};
    for (int i = pos; i > 0; i -= i & (-i)) {
      sum.first += bit[i].first;
      sum.second += bit[i].second;
    }
    return sum;
  }

  pair<ll, ll> RangeSum(int l, int r) {
    pair<ll, ll> x = PrefixSum(r);
    pair<ll, ll> y = PrefixSum(l - 1);
    return {x.first - y.first, x.second - y.second};
  }
} bit1, bit2;

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q;
  cin >> n >> q;

  vector<int> s(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
  }
  vector<int> l(n + 1), r(n + 1);
  stack<int> a;
  for (int i = 1; i <= n; i++) {
    while (!a.empty() && s[a.top()] <= s[i]) {
      a.pop();
    }
    l[i] = (a.empty() ? 1 : a.top() + 1);
    a.push(i);
  }
  stack<int> b;
  for (int i = n; i >= 1; i--) {
    while (!b.empty() && s[b.top()] < s[i]) {
      b.pop();
    }
    r[i] = (b.empty() ? n : b.top() - 1);
    b.push(i);
  }
  vector<pair<pair<int, int>, int>> h1;
  vector<int> c;
  for (int i = 1; i <= n; i++) {
    c.push_back(i);
    h1.push_back({{i, 0}, s[i]});
    h1.push_back({{r[i] + 1, r[i] + 1 - i}, -s[i]});
    if (l[i] > 1) {
      c.push_back(l[i] - 1);
      h1.push_back({{i, i - l[i] + 1}, -s[i]});
      h1.push_back({{r[i] + 1, r[i] + 2 - l[i]}, s[i]});
    }
  }
  vector<pair<pair<int, int>, int>> h2 = h1;
  sort(h1.begin(), h1.end());
  sort(h2.begin(), h2.end(), [](pair<pair<int, int>, int> x, pair<pair<int, int>, int> y) {
    return x.first.second < y.first.second;
  });
  sort(c.begin(), c.end());
  c.erase(unique(c.begin(), c.end()), c.end());
  vector<ll> result(q + 1, 0);
  vector<pair<pair<pair<int, int>, int>, int>> u, v;
  for (int i = 1; i <= q; i++) {
    int t, l, r;
    cin >> t >> l >> r;
    u.push_back({{{r, r - t}, i}, 1});
    u.push_back({{{l - 1, l - t - 1}, i}, -1});
    v.push_back({{{t, r - t}, i}, 1});
    v.push_back({{{t, l - t - 1}, i}, -1});
  }
  sort(u.begin(), u.end());
  int j = -1;
  bit1 = FenwickTree(c.size());
  for (auto i : u) {
    while (j + 1 < h1.size() && h1[j + 1].first.first <= i.first.first.first) {
      j++;
      int x = upper_bound(c.begin(), c.end(), h1[j].first.first - h1[j].first.second) - c.begin();
      bit1.Update(x, { 1LL * (1 - h1[j].first.first) * h1[j].second, h1[j].second });
    }
    int y = lower_bound(c.begin(), c.end(), i.first.first.second) - c.begin() + 1;
    pair<ll, ll> z = bit1.RangeSum(y, c.size());
    result[i.first.second] += i.second * (z.first + z.second * i.first.first.first);
  }
  sort(v.begin(), v.end());
  j = -1;
  bit2 = FenwickTree(c.size());
  for (auto i : v) {
    while (j + 1 < h2.size() && h2[j + 1].first.second <= i.first.first.first) {
      j++;
      int x = upper_bound(c.begin(), c.end(), h2[j].first.first - h2[j].first.second) - c.begin();
      bit2.Update(x, { 1LL * (1 - h2[j].first.second) * h2[j].second, h2[j].second });
    }
    int y = lower_bound(c.begin(), c.end(), i.first.first.second) - c.begin();
    pair<ll, ll> z = bit2.RangeSum(1, y);
    result[i.first.second] += i.second * (z.first + z.second * i.first.first.first);
  }
  for (int i = 1; i <= q; i++) {
    cout << result[i] << '\n';
  }

  return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t5.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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