제출 #382819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382819		ne4eHbKa	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	1 ms	364 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

const int N = 2e5 + 5;
int a[N], q, n;
ll d[N];

struct tree {
    tree *l, *r;
    ll v[2][2];
    void init(int tl) {
        memset(v, -1, sizeof v);
        v[0][0] = 0;
        v[1][1] = abs(d[tl]);
    }
    void upd(int md) {
        bool pairable = d[md] <= 0 && d[md + 1] <= 0 ||
                        d[md] >= 0 && d[md + 1] >= 0;
        for(int i : {0, 1}) {
            for(int j : {0, 1}) {
                v[i][j] = -1;
                umax(v[i][j], l->v[i][0] + r->v[0][j]);
                umax(v[i][j], l->v[i][1] + r->v[0][j]);
                umax(v[i][j], l->v[i][0] + r->v[1][j]);
                if(pairable)
                umax(v[i][j], l->v[i][1] + r->v[1][j]);
            }
        }
    }
    tree(int tl = 1, int tr = n - 1) {
        if(tl < tr) {
            int tm = tl + tr >> 1;
            l = new tree(tl, tm);
            r = new tree(tm + 1, tr);
            upd(tm);
        } else {
            init(tl);
            l = r = 0;
        }
    }
    int ans() {
        ll res = 0;
        for(int i : {0, 1})
            for(int j : {0, 1})
                umax(res, v[i][j]);
        return res;
    }
    void reload(int i, int tl = 1, int tr = n - 1) {
        if(tl == tr) return init(tl);
        int tm = tl + tr >> 1;
        i <= tm
            ? l->reload(i, tl, tm)
            : r->reload(i, tm + 1, tr);
        upd(tm);
    }
};

void solve() {
    cin >> n >> q;
    if(n == 1) {
        while(q--) cout << "0\n";
        return;
    }
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    for(int i = 1; i < n; ++i)
        d[i] = a[i] - a[i - 1];
    tree t {};
    while(q--) {
        int l, r, x;
        cin >> l >> r >> x;
        if(--l) {
            d[l] += x;
            t.reload(l);
        }
        if(r < n)
            d[r] -= x,
            t.reload(r);
        cout << t.ans() << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In member function 'void tree::upd(int)':
Main.cpp:43:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   43 |         bool pairable = d[md] <= 0 && d[md + 1] <= 0 ||
      |                         ~~~~~~~~~~~^~~~~~~~~~~~~~~~~
Main.cpp: In constructor 'tree::tree(int, int)':
Main.cpp:58:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |             int tm = tl + tr >> 1;
      |                      ~~~^~~~
Main.cpp: In member function 'void tree::reload(int, int, int)':
Main.cpp:76:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~

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