Submission #1011712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011712		iah	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	1004 ms	132176 KiB

Main

#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 (stderr)

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 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55