Submission #960257

#TimeUsernameProblemLanguageResultExecution timeMemory
960257ono_de206Sjeckanje (COCI21_sjeckanje)C++14
55 / 110
786 ms32516 KiB
#include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define in insert #define all(x) x.begin(),x.end() #define pb push_back #define eb emplace_back #define ff first #define ss second #define int long long typedef long long ll; typedef vector<int> vi; typedef set<int> si; typedef multiset<int> msi; typedef pair<int, int> pii; typedef vector<pii> vpii; // typedef pair<int, int> P; template<typename T, typename U> ostream & operator << (ostream &out, const pair<T, U> &c) { out << c.first << ' ' << c.second; return out; } template<typename T> ostream & operator << (ostream &out, vector<T> &v) { const int sz = v.size(); for (int i = 0; i < sz; i++) { if (i) out << ' '; out << v[i]; } return out; } template<typename T> istream & operator >> (istream &in, vector<T> &v) { for (T &x : v) in >> x; return in; } template<typename T, typename U> istream & operator >> (istream &in, pair<T, U> &c) { in >> c.first; in >> c.second; return in; } template<typename T> void mxx(T &a, T b){if(b > a) a = b;} template<typename T> void mnn(T &a, T b){if(b < a) a = b;} const int mxn = 2e5 + 10, MXLOG = 22, mod = 1e9 + 7, P = 1181;// D = 1523, N = 2500; const long long inf = 2e18 + 10; int d[mxn * 4][2][2], b[mxn][2], D[mxn]; void up(int i, int x, int y) { b[i][0] = b[x][0]; b[i][1] = b[y][1]; for(int l = 0; l < 2; l++) { for(int r = 0; r < 2; r++) { d[i][l][r] = 0; } } for(int l = 0; l < 2; l++) { for(int r = 0; r < 2; r++) { for(int rr = 0; rr < 2; rr++) { for(int ll = 0; ll < 2; ll++) { if(ll & rr) { if((b[x][1] >= 0 && b[y][0] >= 0) || (b[x][1] <= 0 && b[y][0] <= 0)) { mxx(d[i][l][r], d[x][l][rr] + d[y][ll][r]); } } else { mxx(d[i][l][r], d[x][l][rr] + d[y][ll][r]); } } } } } } void build(int l, int r, int i) { if(l == r) { b[i][0] = b[i][1] = D[l]; d[i][1][1] = abs(D[l]); return; } int m = (l + r) / 2; build(l, m, i * 2); build(m + 1, r, i * 2 + 1); up(i, i * 2, i * 2 + 1); } void update(int l, int r, int i, int x, int y) { if(l == r) { D[l] += y; b[i][0] = b[i][1] = D[l]; d[i][1][1] = abs(D[l]); return; } int m = (l + r) / 2; if(x <= m) update(l, m, i * 2, x, y); else update(m + 1, r, i * 2 + 1, x, y); up(i, i * 2, i * 2 + 1); } void go() { int n, q; cin >> n >> q; int ls; cin >> ls; if(n == 1) { for(int i = 1; i <= q; i++) { cout << 0 << endl; } return; } for(int i = 2; i <= n; i++) { int x; cin >> x; D[i] = x - ls; ls = x; } build(2, n, 1); while(q--) { int l, r, x; cin >> l >> r >> x; if(l > 1) update(2, n, 1, l, x); if(r < n) update(2, n, 1, r + 1, -x); cout << d[1][1][1] << endl; } } signed main() { fast; int t = 1; // cin >> t; while(t--) { go(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...