Submission #699165

# Submission time Handle Problem Language Result Execution time Memory
699165 2023-02-15T22:38:18 Z bane Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
897 ms 31888 KB
#include<bits/stdc++.h>
using namespace std;
 
#ifdef LOCAL
    #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
    #define eprintf(...) 42
#endif
 
//order statistic tree
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<
    T, null_type, less<T>,
    rb_tree_tag, tree_order_statistics_node_update
>;
#define pb push_back
#define mp make_pair
#define ins insert
#define popb pop_back
#define popf pop_front
#define ft front
#define bk back
#define fr first
#define sc second
using ll = long long;
using ld = long double;
using db = double;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<ld,ld>;
using str = string;
const int NAX = (int)1000000;
const int MOD = (int)998244353;
template<int MOD, int RT> struct mint {
	static const int mod = MOD;
	static constexpr mint rt() { return RT; } // primitive root for FFT
	int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int
	mint():v(0) {}
	mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
		if (v < 0) v += MOD; }
	bool operator==(const mint& o) const {
		return v == o.v; }
	friend bool operator!=(const mint& a, const mint& b) { 
		return !(a == b); }
	friend bool operator<(const mint& a, const mint& b) { 
		return a.v < b.v; }
   
	mint& operator+=(const mint& o) { 
		if ((v += o.v) >= MOD) v -= MOD; 
		return *this; }
	mint& operator-=(const mint& o) { 
		if ((v -= o.v) < 0) v += MOD; 
		return *this; }
	mint& operator*=(const mint& o) { 
		v = int((ll)v*o.v%MOD); return *this; }
	mint& operator/=(const mint& o) { return (*this) *= inv(o); }
	friend mint pow(mint a, ll p) {
		mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans; }
	friend mint inv(const mint& a) { assert(a.v != 0); 
		return pow(a,MOD-2); }
		
	mint operator-() const { return mint(-v); }
	mint& operator++() { return *this += 1; }
	mint& operator--() { return *this -= 1; }
	friend mint operator+(mint a, const mint& b) { return a += b; }
	friend mint operator-(mint a, const mint& b) { return a -= b; }
	friend mint operator*(mint a, const mint& b) { return a *= b; }
	friend mint operator/(mint a, const mint& b) { return a /= b; }
};

using mi = mint<MOD,5>;
using vmi = vector<mi>;
using pmi = pair<mi,mi>;
using vpmi = vector<pmi>;
ll n, q;
ll D[300000];
struct Node{
	ll borders[2];
	ll dp[2][2];
	Node(){}
	Node(ll v){
		borders[1] = borders[0] = v;
		memset(dp, 0, sizeof(dp));
		dp[1][1] = abs(v);
	}
	Node Merge(Node right){
		Node res;
		res.borders[0] = borders[0], res.borders[1] = right.borders[1];
		memset(res.dp, 0, sizeof(res.dp));
		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 (c && b){
							//this implies that we merge the two segments because we include [l..r] ->[l...r2]
							if ((borders[1] < 0) == (right.borders[0] < 0)){
								//check signs, dumb to use two same signed borders because we have more optimal arrangement
								res.dp[a][d] = max(res.dp[a][d], dp[a][b] + right.dp[c][d]);
							}
						}else{
							//we do not merge them => they are seperate segments
							res.dp[a][d] = max(res.dp[a][d], dp[a][b] + right.dp[c][d]);
						}
					}
				}
			}
		}
		return res;
	}
};
template<class V, int NV> class SegmentTree{
	public:
			Node t[NV * 3];
			
			void build(int l = 0, int r = n - 2, int node = 1){
				if (l ==r){
					t[node] = Node(D[l]);
					return;
				}
				int mid = (l + r)/2;
				build(l, mid, node * 2);
				build(mid + 1, r, node * 2 + 1);
				t[node] = t[node * 2].Merge(t[node * 2 + 1]);
			}
			void update(int l = 0, int r = n - 2, int node = 1, int pos = 1, ll updval = 0){
				if (l == r){
					t[node] = Node(D[l]);
					return;
				}
				int mid = (l + r)/2;
				if (pos <= mid)update(l,mid,node*2,pos, updval);
				else update(mid+1,r,node*2+1,pos, updval);
				t[node] = t[node * 2].Merge(t[node * 2 + 1]);
			}
};
SegmentTree<int,1<<20>st;

void Task_Sjeckanje(){
	cin >> n >> q;
	vector<ll>a(n);
	memset(D, 0, sizeof(D));
	for (int i = 0; i<n; i++){
		cin >> a[i];
		if (i)D[i - 1] = a[i] - a[i - 1];
	}
	st.build(0,n-2,1);
	while(q--){
		ll b,c, d;
		cin >>  b >> c >> d;
		--b;
		--c;
		if (b){
			D[b-1]+=d;
			st.update(0,n-2,1,b-1, d);
		}
		if(c < n - 1){
			D[c]-=d;
			st.update(0,n-2,1,c, -d);
		}
		//st.build();
		ll ans = 0;
		for(int i = 0; i < 2; i++){
			for (int j =0 ; j < 2; j++){
				ans = max(ans, st.t[1].dp[i][j]);
			}
		}
		cout<<ans<<endl;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("optmilk.in", "r", stdin);
	//freopen("optmilk.out", "w", stdout);
	Task_Sjeckanje();
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 11 ms 3028 KB Output is correct
8 Correct 10 ms 3028 KB Output is correct
9 Correct 11 ms 3028 KB Output is correct
10 Correct 10 ms 3100 KB Output is correct
11 Correct 11 ms 3136 KB Output is correct
12 Correct 9 ms 3128 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 11 ms 3028 KB Output is correct
8 Correct 10 ms 3028 KB Output is correct
9 Correct 11 ms 3028 KB Output is correct
10 Correct 10 ms 3100 KB Output is correct
11 Correct 11 ms 3136 KB Output is correct
12 Correct 9 ms 3128 KB Output is correct
13 Correct 897 ms 31616 KB Output is correct
14 Correct 868 ms 31888 KB Output is correct
15 Correct 866 ms 31796 KB Output is correct
16 Correct 847 ms 31696 KB Output is correct
17 Correct 865 ms 31628 KB Output is correct
18 Correct 839 ms 31792 KB Output is correct