oj.uz

답안 #674389

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
674389 2022-12-24T00:19:35 Z badont Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 666 ms 50728 KB 
#include<bits/stdc++.h>
using namespace std;

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

const LL INF = 1e16;

struct Info {
	array<array<LL, 2>, 2> take;
	LL left, right;

	Info(LL g) : left((g == 0 ? 0LL : g / abs(g))), right(left) {
		this->take[0][0] = 0;
		this->take[1][1] = abs(g);
		this->take[0][1] = this->take[1][0] = -INF;
	}
	Info() : Info(0) {
		this->take[0][0] = this->take[1][1] = -INF;
	}
};

struct Merge {
	Info operator()(const Info& a, const Info& b) {
		Info res;
		F0R (i, 2) F0R(j, 2) {
			F0R (k, 2) F0R (z, 2) if (a.take[i][k] < INF && b.take[z][j] < INF) {
				if (k && z) if (a.right * b.left < 0)
					continue;

				res.take[i][j] = max(res.take[i][j],
					a.take[i][k] + b.take[z][j]
				);
			} 
		}
		res.left = a.left;
		res.right = b.right;
		return res;
	}
};

template<typename T, typename Merge = plus<T>>
struct seg {
	int n;
	vector<T> tr;
	Merge merge;
	seg(int n) : n(n), merge(Merge()), tr((n << 2) + 5, T(0)) {};
	
	seg(vector<LL> a) : seg((int)a.size()) {
		function<void (int, int, int)> build = [&](int z, int l, int r) {
			if (l == r) {
				tr[z] = T(a[l]);
				return;
			}
			
			int mid = (l + r) >> 1;
			build(2 * z, l, mid);
			build(2 * z + 1, mid + 1, r);
			tr[z] = merge(tr[2 * z], tr[2 * z + 1]);
		};
		build(1, 0, n - 1);
	}
	
	void upd(int z, int l, int r, int qg, LL val) {
		if (qg == l && qg == r) {
			tr[z] = T(val);
			return;
		}
		
		int mid = (l + r) >> 1;
		if (qg <= mid) {
			upd(2 * z, l, mid, qg, val);
		} else {
			upd(2 * z + 1, mid + 1, r, qg, val);
		}
		
		tr[z] = merge(tr[2 * z], tr[2 * z + 1]);
	};
	
	T query(int z, int l, int r, int ql, int qr) {
		if (ql > qr) return T(0);
		if (ql == l && qr == r) {
			return tr[z];
		}
		
		int mid = (l + r) >> 1;
		return merge(query(2 * z, l, mid, ql, min(qr, mid)),
					 query(2 * z + 1, mid + 1, r, max(ql, mid + 1), qr));
	};
	
	void upd(int g, LL val) { upd(1, 0, n - 1, g, val); }
	T query(int l, int r) { return query(1, 0, n - 1, l, r); }
};


//var 
LL T;

void solve() {
	LL n, q;
	cin >> n >> q;

	vector<LL> a(n);
	for (auto& u : a)
		cin >> u;

	vector<LL> d(n - 1);
	F0R (i, n - 1) {
		d[i] = a[i] - a[i + 1];
	}

	seg<Info, Merge> tree(d);
	while (q--) {
		LL l, r, x;
		cin >> l >> r >> x;
		l--; r--;

		if (l) {
			d[l - 1] -= x;
			tree.upd(l - 1, d[l - 1]);
		}
		if (r != n - 1) {
			d[r] += x;
			tree.upd(r, d[r]);
		}

		debug(d);

		LL ans = 0;
		F0R (i, 2) F0R(j, 2) ans = max(ans, tree.tr[1].take[i][j]);
		cout << ans << "\n";
	}

}
 
int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);


	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) "zzz"
      |                    ^~~~~
Main.cpp:158:3: note: in expansion of macro 'debug'
  158 |   debug(d);
      |   ^~~~~
Main.cpp: In instantiation of 'seg<T, Merge>::seg(int) [with T = Info; Merge = Merge]':
Main.cpp:80:39:   required from 'seg<T, Merge>::seg(std::vector<long long int>) [with T = Info; Merge = Merge]'
Main.cpp:143:25:   required from here
Main.cpp:77:8: warning: 'seg<Info, Merge>::merge' will be initialized after [-Wreorder]
   77 |  Merge merge;
      |        ^~~~~
Main.cpp:76:12: warning:   'std::vector<Info, std::allocator<Info> > seg<Info, Merge>::tr' [-Wreorder]
   76 |  vector<T> tr;
      |            ^~
Main.cpp:78:2: warning:   when initialized here [-Wreorder]
   78 |  seg(int n) : n(n), merge(Merge()), tr((n << 2) + 5, T(0)) {};
      |  ^~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 1104 KB Output is correct
8 Correct 6 ms 980 KB Output is correct
9 Correct 6 ms 980 KB Output is correct
10 Correct 6 ms 980 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 5 ms 1096 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 1104 KB Output is correct
8 Correct 6 ms 980 KB Output is correct
9 Correct 6 ms 980 KB Output is correct
10 Correct 6 ms 980 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 5 ms 1096 KB Output is correct
13 Correct 663 ms 50212 KB Output is correct
14 Correct 666 ms 50156 KB Output is correct
15 Correct 661 ms 50068 KB Output is correct
16 Correct 649 ms 49964 KB Output is correct
17 Correct 666 ms 49996 KB Output is correct
18 Correct 609 ms 50728 KB Output is correct