oj.uz

Submission #209355

# Submission time Handle Problem Language Result Execution time Memory
209355 2020-03-14T00:47:54 Z eriksuenderhauf Fire (JOI20_ho_t5) C++11
1 / 100
 1000 ms 57716 KB 
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)(x).size()
#define trav(x, a) for (const auto& x: a)
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int inf = 1e9 + 7;
int nxL[N], nxH[N];
array<int,3> arr[N];
vector<array<int,3>> upd[N];
ll ans[N];

struct fenwick {
  vector<ll> BIT;
  int s;

  fenwick(int s) : s(s), BIT(s+1) {}

  void add(int i, ll x) {
    for (i++; i < s; i += i & -i)
      BIT[i] += x;
  }

  ll sum(int i) {
    ll r = 0;
    for (i++; i > 0; i -= i & -i)
      r += BIT[i];
    return r;
  }

  ll sum(int i, int j) {
    if (j < 0)
      return 0;
    return sum(j) - (i <= 0 ? 0 : sum(i - 1));
  }
};

struct segment_tree {
  struct data {
    ll s=0, l=1;
    data() {}
    data(ll s, ll l) : s(s), l(l) {}
  };
  typedef ll operation;
  static data combine(data dl, data dr) {
    return {dl.s + dr.s, dl.l + dr.l};
  }
  static data calculate(operation o, data d) {
    return {o * d.l + d.s, d.l};
  }
  static operation merge(operation ot, operation ob) {
    return ot + ob;
  }
  int n, h;
  vector<data> t;
  vector<operation> o;
  segment_tree(int n = 0) : n(n), h(32 - __builtin_clz(n)), t(2 * n), o(n) {
    for (int i = 0; i < n; i++)
      t[i + n] = {0, 1};
    for (int x = n - 1; x > 0; x--)
      t[x] = combine(t[x << 1], t[x << 1 | 1]);
  }
  segment_tree(vector<data> & a) : segment_tree(a.size()) {
    for (int i = 0; i < n; i++)
      t[i + n] = a[i];
    for (int x = n - 1; x > 0; x--)
      t[x] = combine(t[x << 1], t[x << 1 | 1]);
  }
  void apply(int x, operation op) {
    t[x] = calculate(op, t[x]);
    if (x < n)
      o[x] = merge(op, o[x]);
  }
  void push(int x) {
    for (int s = h; s > 0; s--) {
      int c = x >> s;
      apply(c << 1, o[c]);
      apply(c << 1 | 1, o[c]);
      o[c] = operation();
    }
  }
  void build(int x) {
    while (x >>= 1)
      t[x] = calculate(o[x], combine(t[x << 1], t[x << 1 | 1]));
  }
  // set the data at the position i
  void setValue(int i, data d) {
    i += n;
    push(i);
    t[i] = d;
    build(i);
  }
  // query the data on the range [l, r[
  ll query(int l, int r) {
    l += n; r += n;
    push(l); push(r - 1);
    data dl, dr;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        dl = combine(dl, t[l++]);
      if (r & 1)
        dr = combine(t[--r], dr);
    }
    return combine(dl, dr).s;
  }
  // apply an operation on the range [l, r[
  void apply(int l, int r, operation op) {
    l += n; r += n;
    push(l); push(r - 1);
    int xl = l, xr = r;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        apply(l++, op);
      if (r & 1)
        apply(--r, op);
    }
    build(xl); build(xr - 1);
  }
};

#define log2(x) (31 - __builtin_clz(x))

struct sparse_table {
  int n;
  vector<segment_tree::data> a;
  vector<vector<int>> st;
  int combine(int dl, int dr) {
    return a[dl].s > a[dr].s ? dl : dr;
  }
  sparse_table() {}
  sparse_table(vector<segment_tree::data> & a) : n(a.size()), a(a), st(log2(n) + 1, vector<int>(n)) {
    for (int i = 0; i < n; i++)
      st[0][i] = i;
    for (int j = 1; 1 << j <= n; j++)
      for (int i = 0; i + (1 << j) <= n; i++)
        st[j][i] = combine(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
  }
  // query the data on the range [l, r[
  int query(int l, int r) {
    int s = log2(r - l);
    return combine(st[s][l], st[s][r - (1 << s)]);
  }
};

int main() {
  int n, q; scanf("%d %d", &n, &q);
  int n2 = n+2;
  while (n2 & (n2-1)) n2++;
  vector<segment_tree::data> s(n2);
  fenwick f(n2);
  s[0] = s[n+1] = {inf, 1};
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &s[i].s);
    s[i].l = 1;
  }
  stack<int> st; st.push(n+1);
  for (int i = n; i; i--) {
    while (!st.empty() && s[st.top()].s < s[i].s)
      st.pop();
    nxH[i] = st.top();
    st.push(i);
  }
  while (!st.empty()) st.pop();
  st.push(0);
  for (int i = 1; i <= n; i++) {
    while (!st.empty() && s[st.top()].s < s[i].s)
      st.pop();
    nxL[i] = st.top();
    st.push(i);
  }
  sparse_table sp(s);
  for (int i = 1; i <= n; i++) {
    if (i+1 <= nxH[i]-1) {
      int v = s[i].s - s[sp.query(i+1, nxH[i])].s;
      f.add(i, v);
      upd[nxH[i]-i].pb({i+1, nxH[i]-1, v});
    }
    if (nxL[i]+1 <= i-1 && nxL[i] != 0 && s[nxL[i]].s != s[i].s) {
      int v = s[i].s - s[sp.query(nxL[i]+1, i)].s;
      f.add(nxL[i], v);
      upd[i-nxL[i]].pb({nxL[i]+1, i-1, v});
    }
  }
  segment_tree seg(s);
  for (int i = 0; i < q; i++) {
    for (int j = 0; j < 3; j++)
      scanf("%d", &arr[i][j]);
    upd[arr[i][0]].pb({-i, arr[i][1], arr[i][2]});
  }
  for (int i = 1; i <= n; i++) {
    trav(j, upd[i]) {
      if (j[0] > 0) {
        seg.apply(j[0], j[1]+1, j[2]);
        f.add(j[0]-1, -j[2]);
      }
    }

    trav(j, upd[i]) {
      if (j[0] <= 0) {
        ans[-j[0]] = seg.query(j[1], j[2]+1);
        for (int k = 1; k <= i; k++)
          ans[-j[0]] += f.sum(j[1]-k, j[2]-k);
      }
    }
  }
  for (int i = 0; i < q; i++)
    printf("%lld\n", ans[i]);
}

Compilation message

ho_t5.cpp: In constructor 'fenwick::fenwick(int)':
ho_t5.cpp:20:7: warning: 'fenwick::s' will be initialized after [-Wreorder]
   int s;
       ^
ho_t5.cpp:19:14: warning:   'std::vector<long long int> fenwick::BIT' [-Wreorder]
   vector<ll> BIT;
              ^~~
ho_t5.cpp:22:3: warning:   when initialized here [-Wreorder]
   fenwick(int s) : s(s), BIT(s+1) {}
   ^~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:151:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int n, q; scanf("%d %d", &n, &q);
             ~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp:158:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &s[i].s);
     ~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp:192:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &arr[i][j]);
       ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Execution timed out 1100 ms 55540 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Execution timed out 1103 ms 57716 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1103 ms 55760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 7 ms 5112 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 8 ms 5112 KB Output is correct
6 Correct 8 ms 5112 KB Output is correct
7 Correct 8 ms 5112 KB Output is correct
8 Correct 8 ms 5112 KB Output is correct
9 Correct 8 ms 5112 KB Output is correct
10 Correct 8 ms 5112 KB Output is correct
11 Correct 8 ms 5112 KB Output is correct
12 Correct 8 ms 5112 KB Output is correct
13 Correct 8 ms 5112 KB Output is correct
14 Correct 9 ms 5112 KB Output is correct
15 Correct 8 ms 5112 KB Output is correct
16 Correct 8 ms 5112 KB Output is correct
17 Correct 8 ms 5112 KB Output is correct
18 Correct 8 ms 5112 KB Output is correct
19 Correct 8 ms 5112 KB Output is correct
20 Correct 8 ms 5112 KB Output is correct
21 Correct 9 ms 5112 KB Output is correct
22 Correct 8 ms 5112 KB Output is correct
23 Correct 8 ms 5112 KB Output is correct
24 Correct 8 ms 5112 KB Output is correct
25 Correct 8 ms 5112 KB Output is correct
26 Correct 8 ms 5112 KB Output is correct
27 Correct 8 ms 5112 KB Output is correct
28 Correct 8 ms 5112 KB Output is correct
29 Correct 8 ms 5112 KB Output is correct
30 Correct 8 ms 5112 KB Output is correct
31 Correct 8 ms 5112 KB Output is correct
32 Correct 7 ms 5112 KB Output is correct
33 Execution timed out 1097 ms 57588 KB Time limit exceeded
34 Halted 0 ms 0 KB -