oj.uz

답안 #537827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537827 2022-03-15T16:02:52 Z Cantfindme Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

const int maxn = 100010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;

int n, Q;
int A[maxn];
int diff[maxn];

struct dat {
	int v, vs, ve;
	int ss, se;
	dat () {}
	dat (int nv) {
		v = vs = ve = abs(nv);
		ss = se = (nv < 0);
	}

	void merge(const dat &a, const dat &b) {
		v = a.v + b.v;
		if (a.se != b.ss) v -= min(a.ve, b.vs);
		
		vs = a.vs;
		ve = b.ve;
		ss = a.ss;
		se = b.se;
	}
};

struct node {
	int s, m, e;
	dat d;
	node *l, *r;
	node (int _s, int _e) {
		s = _s; e = _e; m = (s+e)/2;
		if (s != e) {
			l = new node(s,m);
			r = new node(m+1,e);
			d.merge(l -> d, r -> d);
			// cout << s << " " << e << " " << d.v << "\n";
		} else {
			diff[s] = A[s] - A[s-1];
			d = dat(A[s] - A[s-1]);
		}
	}

	void upd(int x, int nv) {
		if (s == e) {
			d = dat(nv);
		} else {
			if (x > m) r -> upd(x,nv);
			else if (x <= m) l -> upd(x,nv);
			d.merge(l -> d, r -> d);
			// cout << "UPD: " << s << " " << e << " " << d.v << "\n";
		}
	}

	int rmq() {
		return d.v;
	}
} *root;

int32_t main() {
	FAST
	// ifstream cin("input.txt");

	cin >> n >> Q;
	for (int i =1;i<=n;i++) cin >> A[i];
	A[0] = A[1];

	root = new node(1,n);
	// cout << root -> rmq() << "\n";

	for (int q = 0; q<Q;q++) {
		int l, r, x; cin >> l >> r >> x;
		
		if (l != 1) {
			diff[l] += x;
			root -> upd(l, diff[l]);
		}

		if (r+1 <= n) {
			diff[r + 1] -= x;
			root -> upd(r+1, diff[r+1]);
		}	

		// for (int i =1;i<=n;i++) cout << diff[i] << " ";
		// cout << "\n";
		cout << root -> rmq() << "\n";
	}

}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -