제출 #768968

#제출 시각아이디문제언어결과실행 시간메모리
768968chanhchuong123Sjeckanje (COCI21_sjeckanje)C++14
110 / 110
391 ms42172 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 200200; int n, q; int a[MAX]; struct node { long long dp[2][2]; int value[2]; node(int _x = 0) { memset(dp, 0, sizeof dp); dp[1][1] = abs(_x); value[0] = value[1] = _x; } }; node st[MAX << 2]; node merge(const node &u, const node &v) { node res; res.value[0] = u.value[0]; res.value[1] = v.value[1]; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { res.dp[i][j] = max(res.dp[i][j], u.dp[i][0] + v.dp[0][j]); res.dp[i][j] = max(res.dp[i][j], u.dp[i][0] + v.dp[1][j]); res.dp[i][j] = max(res.dp[i][j], u.dp[i][1] + v.dp[0][j]); if (1LL * u.value[1] * v.value[0] >= 0) res.dp[i][j] = max(res.dp[i][j], u.dp[i][1] + v.dp[1][j]); } } return res; } void build(int id, int l, int r) { if (l == r) st[id] = node(a[l]); else { int mid = l + r >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); st[id] = merge(st[id << 1], st[id << 1 | 1]); } } void update(int id, int l, int r, int pos) { if (l == r) st[id] = node(a[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] = merge(st[id << 1], st[id << 1 | 1]); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i < n; ++i) { a[i] = a[i + 1] - a[i]; } build(1, 1, n - 1); while (q--) { int l, r, x; cin >> l >> r >> x; a[r] -= x; if (r < n) update(1, 1, n - 1, r); if (l > 1) a[l - 1] += x, update(1, 1, n - 1, l - 1); cout << max({st[1].dp[0][0], st[1].dp[0][1], st[1].dp[1][0], st[1].dp[1][1]}) << '\n'; } return 0; }

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

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