Submission #1157551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157551		Zero_OP	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	514 ms	31576 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define rep(i, l, r) for(int i = (l); i < (r); ++i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define sum_of(v) accumluate(all(v), 0ll)
#define max_of(v) *max_element(all(v))
#define min_of(v) *min_element(all(v))
#define pb push_back
#define eb emplace_back

#define dbg(x) "[" #x " = " << (x) << "]"
#define inputFile(task) freopen(task, "r", stdin);
#define outputFile(task) freopen(task, "w", stdout);

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ull = unsigned long long;
using ldb = long double;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vb = vector<bool>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      inputFile("task.inp");
      outputFile("task.out");
#endif // LOCAL
}

const int MAX = 2e5 + 5;

int N, Q;
ll a[MAX], d[MAX];

struct Node{
      ll f[2][2];
      Node(){
            memset(f, 0, sizeof(f));
      }

      void init(int x){
            memset(f, 0, sizeof(f));
            if(x < 0) f[1][1] = -x;
            else f[0][0] = x;
      }

      friend Node operator + (const Node& a, const Node& b){
            Node c;
            FOR(i, 0, 2){
                  FOR(j, 0, 2){
                        FOR(k, 0, 2){
                              FOR(l, 0, 2){
                                    maximize(c.f[i][l], a.f[i][j]);
                                    maximize(c.f[i][l], b.f[k][l]);
                                    if(j == k) maximize(c.f[i][l], a.f[i][j] + b.f[k][l]);
                              }
                        }
                  }
            }
            return c;
      }
};

Node st[MAX << 2];

void build(int id, int l, int r){
      if(l == r) st[id].init(d[l]);
      else{
            int mid = l + r >> 1;
            build(id << 1, l, mid);
            build(id << 1 | 1, mid + 1, r);
            st[id] = st[id << 1] + st[id << 1 | 1];
      }
}

void update(int id, int l, int r, int pos){
      if(l == r) st[id].init(d[l]);
      else{
            int mid = l + r >> 1;
            if(pos <= mid) update(id << 1, l, mid, pos);
            else update(id << 1 | 1, mid + 1, r, pos);
            st[id] = st[id << 1] + st[id << 1 | 1];
      }
}

ll find_result(){
      ll result = 0;
      FOR(i, 0, 2) FOR(j, 0, 2) maximize(result, st[1].f[i][j]);
      return result;
}

int main(){
      setIO();

      cin >> N >> Q;
      FOR(i, 0, N) {
            cin >> a[i];
            d[i] += a[i];
            d[i+1] -= a[i];
      }

      build(1, 1, N-1);

      while(Q--){
            int l, r, x;
            cin >> l >> r >> x;
            --l;
            d[l] += x;
            d[r] -= x;

//            FOR(i, 0, N) cout << d[i] << " \n"[i == N-1];

            if(l>0) update(1, 1, N-1, l);
            if(r<N) update(1, 1, N-1, r);

            cout << find_result() << '\n';
      }


      return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55