oj.uz

Submission #938920

# Submission time Handle Problem Language Result Execution time Memory
938920 2024-03-05T20:34:47 Z RadicaI Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 327 ms 50892 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 3 ms 1148 KB Output is correct
8 Correct 3 ms 1116 KB Output is correct
9 Correct 3 ms 1240 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 3 ms 1152 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 3 ms 1148 KB Output is correct
8 Correct 3 ms 1116 KB Output is correct
9 Correct 3 ms 1240 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 3 ms 1152 KB Output is correct
13 Correct 327 ms 50344 KB Output is correct
14 Correct 319 ms 50212 KB Output is correct
15 Correct 314 ms 50380 KB Output is correct
16 Correct 324 ms 50120 KB Output is correct
17 Correct 310 ms 50272 KB Output is correct
18 Correct 295 ms 50892 KB Output is correct