제출 #1099230

#제출 시각아이디문제언어결과실행 시간메모리
1099230hiensumiSjeckanje (COCI21_sjeckanje)C++14
110 / 110
293 ms30020 KiB
#include <bits/stdc++.h> using namespace std; #define fod(i,a,b) for(int i = (int) (a); i <= (int) (b); i++) #define fok(i,a,b) for(int i = (int) (a); i >= (int) (b); i--) #define ll long long #define pb pusi_back #define pii pair<int,int> #define mp make_pair #define fi first #define se second #define el '\n' #define ve vector #define vi ve<int> #define vll ve<ll> #define mask(a) (1LL<<(a)) #define BIT(msk,i) (msk>>(i)&1LL) using namespace std; template <class T> bool mini(T &a, T b){ return (a > (b)) ? a = (b), 1 : 0; } template <class T> bool maxi(T &a, T b){ return (a < (b)) ? a = (b), 1 : 0; } #define name "sjeckanje" int n, q; const int N = 2e5; ll a[N + 5]; ll dp[N + 5][3]; int solve(){ dp[0][0] = 0; dp[0][1] = dp[0][2] = -1e15; fod(i,1,n){ dp[i][0] = max({dp[i-1][1] - a[i], dp[i-1][2] + a[i], dp[i-1][0]}); dp[i][1] = max(dp[i-1][1], dp[i-1][0] + a[i]); dp[i][2] = max(dp[i-1][2], dp[i-1][0] - a[i]); } return dp[n][0]; } ll d[N + 5]; ll st[4 * N][2][2]; void upd(int u, int i = 1, int l = 1, int r = n - 1){ if(r < u or u < l) return; if(l == r){ st[i][1][1] = abs(d[l]); return; } int mid = l + r >> 1; upd(u,i<<1,l,mid); upd(u,i<<1|1,mid+1,r); st[i][1][1] = max(st[i<<1][1][0] + st[i<<1|1][1][1], st[i<<1][1][1] + st[i<<1|1][0][1]); st[i][1][0] = max(st[i<<1][1][0] + st[i<<1|1][1][0], st[i<<1][1][1] + st[i<<1|1][0][0]); st[i][0][1] = max(st[i<<1][0][0] + st[i<<1|1][1][1], st[i<<1][0][1] + st[i<<1|1][0][1]); st[i][0][0] = max(st[i<<1][0][0] + st[i<<1|1][1][0], st[i<<1][0][1] + st[i<<1|1][0][0]); if((d[mid] >= 0 and d[mid + 1] >= 0) or (d[mid] <= 0 and d[mid + 1] <= 0)){ st[i][1][1] = max(st[i<<1][1][0], st[i<<1][1][1]) + max(st[i<<1|1][0][1], st[i<<1|1][1][1]); st[i][1][0] = max(st[i<<1][1][0], st[i<<1][1][1]) + max(st[i<<1|1][0][0], st[i<<1|1][1][0]); st[i][0][1] = max(st[i<<1][0][0], st[i<<1][0][1]) + max(st[i<<1|1][0][1], st[i<<1|1][1][1]); st[i][0][0] = max(st[i<<1][0][0], st[i<<1][0][1]) + max(st[i<<1|1][0][0], st[i<<1|1][1][0]); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> q; fod(i,1,n) cin >> a[i]; fod(i,1,n-1){ d[i] = a[i+1] - a[i]; upd(i); } while(q--){ int l, r, x; cin >> l >> r >> x; // fod(i,l,r) a[i] += x; // cout << solve() << el; d[r] -= x; upd(r); if(l-1){ d[l-1] += x; upd(l-1); } cout << max(max(st[1][0][0], st[1][1][1]), max(st[1][0][1], st[1][1][0])) << el; } return 0; }

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

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