Submission #938920

#	Time	Username	Problem	Language	Result	Execution time	Memory
938920		RadicaI	Sjeckanje (COCI21_sjeckanje)	C++17	110 / 110	327 ms	50892 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pi pair<int,int>
#define pb push_back
#define V vector
#define vi V<int>
#define mi map<int,int>
#define MOD 1000000007
#define MOD2 998244353
#define mp make_pair
#define ins insert
#define qi queue<int>
#define pqi priority_queue<int>
#define si set<int>
#define v2i V<vi>
#define v3i V<v2i>
#define v4i V<v3i>
#define v5i V<v4i>
#define INF 1e18
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl "\n"
#define lb lower_bound
#define ub upper_bound
#define print(x) cout << x<<" ";
#define vpi V<pi>
#define Y cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define msi multiset<int>
#define F first
#define S second
#define ld long double
#define RE return;
#define IMP cout<<-1<<endl;return;
using namespace std;

template <typename T>
std::istream& operator>>(std::istream& in, std::vector<T>& vec) {
    for (T& x : vec) {
        in >> x;
    }
    return in;
}

struct Node{
	int left=-1; int right=-1;
	int val=0;
	int misr = 0; int misl = 0; int missb = 0;
};

vector<int> diff; 
V<Node> seg;

Node merge(Node a, Node b){
	Node n; n.left = a.left; n.right = b.right;
	if(a.right==b.left){
		n.val = a.val + b.val;
		n.misr = a.val + b.misr;
		n.misl = a.misl+ b.val;
		n.missb = a.misl + b.misr; 
	}else{
		n.val = max(a.val + b.misl, a.misr + b.val);
		n.misr = max(a.val + b.missb, a.misr + b.misr);
		n.misl = max(a.missb+b.val, a.misl + b.misl);
		n.missb = max(a.missb + b.misr, a.misl + b.missb);
	}
	return n;
};

void build(int node, int l, int r){
	if(l==r){
		Node ne; ne.left = ne.right = (diff[l]>=0);
		ne.val = abs(diff[l]);
		seg[node] = ne;
		return;
	}
	int mid = (l+r)/2;
	build(2*node, l, mid); build(2*node+1, mid+1, r);
	seg[node] = merge(seg[2*node], seg[2*node+1]);
}

void update(int node, int l, int r, int i){
	if(l==r){
		Node ne; ne.left = ne.right = (diff[l]>=0);
		ne.val = abs(diff[l]);
		seg[node] = ne;
		return;
	}
	int mid = (l+r)/2;
	if(i<=mid)update(2*node, l, mid,i); 
	else update(2*node+1, mid+1, r,i);
	seg[node] = merge(seg[2*node], seg[2*node+1]);
}

signed main(){
	fastio;
	int n,q; cin >> n>>q; seg.resize(4*n);
	vi a(n); cin >> a; for(int i=0; i<n-1; i++) diff.pb(a[i+1]-a[i]);
	build(1,0,n-2);
	while(q--){
		int l, r,v; cin >>l>>r>>v;
		if(l>1) diff[l-2] += v, update(1,0,n-2,l-2);
		if(r<n) diff[r-1] -=v, update(1, 0, n-2, r-1); 
		
		cout << seg[1].val<<endl;
	}
	
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55