제출 #794996

#제출 시각아이디문제언어결과실행 시간메모리
794996hafoSjeckanje (COCI21_sjeckanje)C++14
110 / 110
521 ms23164 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define pb push_back #define pa pair<int, int> #define pall pair<ll, int> #define fi first #define se second #define TASK "test" #define Size(x) (int) x.size() #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;} template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;} const int MOD = 1e9 + 7; const int LOG = 20; const int maxn = 2e5 + 7; const ll oo = 1e18 + 69; int n, q, l, r, x, d[maxn]; ll a[maxn]; struct ST { struct node { ll sum[2][2]; }; node st[4 * maxn]; void merge(int id, int l, int r) { int mid = l + r >> 1, id1 = (id << 1), id2 = (id << 1 | 1); bool ex = 0; if((d[mid] < 0 && d[mid + 1] > 0) || (d[mid] > 0 && d[mid + 1] < 0)) ex = 1; memset(st[id].sum, 0, sizeof st[id].sum); for(int a = 0; a < 2; a++) { for(int b = 0; b < 2; b++) { for(int c = 0; c < 2; c++) { for(int d = 0; d < 2; d++) { if(ex == 1 && b != c) continue; maxi(st[id].sum[a][d], st[id1].sum[a][b] + st[id2].sum[c][d]); } } } } } void build(int id, int l, int r) { if(l == r) { st[id].sum[0][1] = abs(d[l]); st[id].sum[0][0] = 0; st[id].sum[1][0] = 0; st[id].sum[1][1] = 0; return; } int mid = l + r >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); merge(id, l, r); } void update(int id, int l, int r, int pos) { if(pos < l || pos > r) return; if(l == r) { st[id].sum[0][1] = abs(d[l]); st[id].sum[0][0] = 0; st[id].sum[1][0] = 0; st[id].sum[1][1] = 0; return; } int mid = l + r >> 1; update(id << 1, l, mid, pos); update(id << 1 | 1, mid + 1, r, pos); merge(id, l, r); } } st; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen(TASK".inp", "r", stdin); //freopen(TASK".out", "w", stdout); cin>>n>>q; for(int i = 1; i <= n; i++) cin>>a[i]; for(int i = 1; i <= n; i++) d[i] = (i == n ? 0:a[i] - a[i + 1]); st.build(1, 1, n); while(q--) { cin>>l>>r>>x; if(l - 1 >= 1) { d[l - 1] -= x; st.update(1, 1, n, l - 1); } if(r != n) { d[r] += x; st.update(1, 1, n, r); } ll ans = 0; for(int i = 0; i < 2; i++) for(int j = 0; j < 2; j++) maxi(ans, st.st[1].sum[i][j]); cout<<ans<<"\n"; } return 0; }

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

Main.cpp: In member function 'void ST::merge(int, int, int)':
Main.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mid = l + r >> 1, id1 = (id << 1), id2 = (id << 1 | 1);
      |                   ~~^~~
Main.cpp: In member function 'void ST::build(int, int, int)':
Main.cpp:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void ST::update(int, int, int, int)':
Main.cpp:73:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int mid = l + r >> 1;
      |                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...