Submission #1044618

#TimeUsernameProblemLanguageResultExecution timeMemory
1044618underwaterkillerwhaleSjeckanje (COCI21_sjeckanje)C++17
0 / 110
1 ms2392 KiB
#include <bits/stdc++.h> #define ll long long #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define MP make_pair #define fs first #define se second #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define SZ(v) (int)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 2e5 + 7; const int Mod = 1e9 + 7; const ll INF = 1e18; const ll BASE = 137; int n, Q; int a[N]; struct Query { int l, r, X; }qr[N]; struct Segment_Tree { struct Node { ll f[2][2], ps, ss; }; int m; Node st[N << 2]; void init (int n) { m = n; rep (i, 1, n << 2) st[i].f[0][1] = st[i].f[1][0] = -INF, st[i].f[1][1] = st[i].f[0][0] = 0; } Node mer (Node lf, Node rt) { Node cur; cur.ps = lf.ps; cur.ss = rt.ss; rep (i, 0, 1) rep (t, 0, 1) { cur.f[i][t] = -INF; rep (j, 0, 1) rep (k, 0, 1) { if (lf.ss != rt.ps) { if (j != k) cur.f[i][t] = max(cur.f[i][t], lf.f[i][j] + rt.f[k][t]); } else { cur.f[i][t] = max(cur.f[i][t], lf.f[i][j] + rt.f[k][t]); } } } return cur; } void update (int id, int l, int r, int pos, ll val) { if (l > pos || r < pos) return; if (l == r) { st[id].ps += val; st[id].ss += val; st[id].f[1][1] = abs(st[id].ps); return; } int mid = l + r >> 1; update (id << 1, l, mid, pos, val); update (id << 1 | 1, mid + 1, r, pos, val); st[id] = mer (st[id << 1], st[id << 1 | 1]); } void update (int pos, int val) { update (1, 1, m, pos, val); } }ST; void solution () { cin >> n >> Q; rep (i, 1, n) cin >> a[i]; ST.init(n - 1); rep (i, 1, n - 1) ST.update (i, a[i + 1] - a[i]); rep (q, 1, Q) { cin >> qr[q].l >> qr[q].r >> qr[q].X; ST.update(qr[q].l - 1, qr[q].X); ST.update(qr[q].r, -qr[q].X); ll res = 0; rep (i, 0, 1) rep (j, 0, 1) res = max(res, ST.st[1].f[i][j]); cout << res<<"\n"; } } #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); int main () { // file("c"); ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug challenge +2 4 1 2 3 4 2 0 3 2 1 */

Compilation message (stderr)

Main.cpp: In member function 'void Segment_Tree::update(int, int, int, int, long long int)':
Main.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...