oj.uz

Submission #1011712

# Submission time Handle Problem Language Result Execution time Memory
1011712 2024-07-01T07:15:16 Z iah Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 1004 ms 132176 KB 
#include<bits/stdc++.h>
using namespace std;

#define NAME "division"
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())

constexpr ll inf = 1e18;

struct Fenwick {
  int n;
  vector < ll > b;

  void init(int _n) {
    n = _n;
    b.assign(n + 1, 0);
  }

  void update(int i, ll val) {
    for (; i <= n; i += (i & (-i))) {
      b[i] += val;
    }
  }

  int get(int i) {
    int res = 0;

    for (; i > 0; i -= (i & (-i))) {
      res += b[i];
    }

    return res;
  }
}ft;

struct SegTree {
  int n;
  struct _data {
    bool left, right;
  };

  vector < _data > cmp;
  vector < vector < vector < ll > > > b;

  void init(int _n) {
    n = _n;
    b.assign(n * 4 + 1, vector < vector < ll > > (2, vector < ll > (2, 0)));
    cmp.assign(n * 4 + 1, {0, 0});
  }

  void combine(int id) {
    int l = id << 1, r = id << 1 | 1;
    cmp[id].left = cmp[l].left;
    cmp[id].right = cmp[r].right;
    for (int xl = 0; xl < 2; xl ++) {
      for (int yr = 0; yr < 2; yr ++) {
        b[id][xl][yr] = -inf;
//        cout << id << " " << xl << " " << yr << ":\n";
        for (int xr = 0; xr < 2; xr ++) {
          for (int yl = 0; yl < 2; yl ++) {
            if (cmp[l].right == cmp[r].left) {
              b[id][xl][yr] = max(b[id][xl][yr], b[l][xl][xr] + b[r][yl][yr]);
            }
            if (xr || yl) {
              b[id][xl][yr] = max(b[id][xl][yr], b[l][xl][xr] + b[r][yl][yr]);
//              cout << b[l][xl][xr] << " " << b[r][yl][yr] << " " << b[id][xl][yr] << "\n";
            }
          }
        }
//        cout << b[id][xl][yr] << "\n";
      }
    }
  }

  void _update(int id, int l, int r, int i, int val) {
    if (l > i || i > r) {
      return;
    }

    if (l == r) {
      cmp[id] = {val > 0, val > 0};
      b[id][0][0] = abs(val);
      b[id][0][1] = 0;
      b[id][1][0] = 0;
      b[id][1][1] = 0;
      return;
    }

    int mid = (l + r) >> 1;
    _update(id << 1, l, mid, i, val);
    _update(id << 1 | 1, mid + 1, r, i, val);
    combine(id);

//    cout << id << " " << l << " " << r << "\n";
//    for (int x = 0; x < 2; x ++) {
//      for (int y = 0; y < 2; y ++) {
//        cout << b[id][x][y] << " ";
//      }
//    }
//    cout << "\n";
  }

  void update(int i, ll val) {
//    cout << "update " << i << " " << val << "\n";
    _update(1, 1, n, i, val);
  }
}seg;

signed main() {
  if (fopen(NAME".inp", "r")) {
    freopen(NAME".inp", "r", stdin);
    freopen(NAME".out", "w", stdout);
  }
  cin.tie(0)->sync_with_stdio(0);

  int n, q;
  cin >> n >> q;
  seg.init(n - 1);
  ft.init(n);

  for (int i = 1; i <= n; i ++) {
    ll x;
    cin >> x;
    ft.update(i, x);
    ft.update(i + 1, -x);
  }

  for (int i = 2; i <= n; i ++) {
    seg.update(i - 1, ft.get(i) - ft.get(i - 1));
  }

  for (; q --;) {
    int l, r, x;
    cin >> l >> r >> x;
    ft.update(l, x);
    ft.update(r + 1, -x);

    seg.update(l - 1, ft.get(l) - ft.get(l - 1));
    if (r + 1 <= n) {
      seg.update(r, ft.get(r + 1) - ft.get(r));
    }
    ll ans = -inf;
    for (int l = 0; l < 2; l ++) {
      for (int r = 0; r < 2; r ++) {
        ans = max(ans, seg.b[1][l][r]);
      }
    }

    cout << ans << "\n";
  }

  return 0;
}

Compilation message

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 8 ms 2396 KB Output is correct
8 Correct 8 ms 2424 KB Output is correct
9 Correct 8 ms 2292 KB Output is correct
10 Correct 8 ms 2396 KB Output is correct
11 Correct 8 ms 2396 KB Output is correct
12 Correct 7 ms 2396 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 8 ms 2396 KB Output is correct
8 Correct 8 ms 2424 KB Output is correct
9 Correct 8 ms 2292 KB Output is correct
10 Correct 8 ms 2396 KB Output is correct
11 Correct 8 ms 2396 KB Output is correct
12 Correct 7 ms 2396 KB Output is correct
13 Correct 973 ms 131608 KB Output is correct
14 Correct 899 ms 131664 KB Output is correct
15 Correct 1004 ms 131496 KB Output is correct
16 Correct 893 ms 131572 KB Output is correct
17 Correct 923 ms 131736 KB Output is correct
18 Correct 896 ms 132176 KB Output is correct