제출 #1369146

#제출 시각아이디문제언어결과실행 시간메모리
1369146kaiboyTwo Dishes (JOI19_dishes)C++20
100 / 100
2732 ms136736 KiB
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const       int   N = 1000000;
const       int   M = 1000000;
const       int  N_ = 1 << 20;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

long long aa[N + 1], ss[N + 1], bb[M + 1], tt[M + 1];
int pp[N + 1], qq[M + 1];
vector<pair<int, int>> qu[N + 1];
long long st[N_ << 1], lz_s[N_], lz_a[N_], h_, n_;

void put(int i, long long s, long long a) {
	st[i] = max(st[i] + s, a);
	if (i < n_) {
		lz_s[i] += s;
		lz_a[i] = max(lz_a[i] + s, a);
	}
}

void pus(int i) {
	if (lz_s[i] || lz_a[i] != -INF) {
		int l = i << 1, r = l ^ 1;
		put(l, lz_s[i], lz_a[i]);
		put(r, lz_s[i], lz_a[i]);
		lz_s[i] = 0, lz_a[i] = -INF;
	}
}

void pul(int i) {
	if (!lz_s[i] && lz_a[i] == -INF) {
		int l = i << 1, r = l ^ 1;
		st[i] = max(st[l], st[r]);
	}
}

void push(int i) {
	for (int h = h_; h; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i >>= 1)
		pul(i);
}

void build(int n) {
	for (h_ = 0, n_ = 1; n_ < n; h_++, n_ <<= 1)
		;
	for (int i = 0; i < n_; i++)
		st[i + n_] = lz_s[i] = 0, lz_a[i] = -INF;
	for (int i = n_ - 1; i; i--)
		pul(i);
}

void update_s(int l, int r, int a) {
	int l_ = l += n_, r_ = r += n_;
	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			put(l++, a, -INF);
		if (!(r & 1))
			put(r--, a, -INF);
	}
	pull(l_), pull(r_);
}

void update_a(int l, int r, long long a) {
	int l_ = l += n_, r_ = r += n_;
	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			put(l++, 0, a);
		if (!(r & 1))
			put(r--, 0, a);
	}
	pull(l_), pull(r_);
}

long long query(int i) {
	push(i += n_);
	return st[i];
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> aa[i] >> ss[i] >> pp[i], aa[i] += aa[i - 1];
	for (int j = 1; j <= m; j++)
		cin >> bb[j] >> tt[j] >> qq[j], bb[j] += bb[j - 1];
	long long s = 0;
	for (int i = 1; i <= n; i++) {
		if (aa[i] > ss[i])
			continue;
		int lower = 0, upper = m + 1;
		while (upper - lower > 1) {
			int j = lower + upper >> 1;
			if (aa[i] + bb[j] <= ss[i])
				lower = j;
			else
				upper = j;
		}
		int j = lower;
		if (j < m)
			qu[i].push_back({ j, pp[i] });
		else
			s += pp[i];
	}
	for (int j = 1; j <= m; j++) {
		if (bb[j] > tt[j])
			continue;
		int lower = 0, upper = n + 1;
		while (upper - lower > 1) {
			int i = lower + upper >> 1;
			if (aa[i] + bb[j] <= tt[j])
				lower = i;
			else
				upper = i;
		}
		int i = lower;
		s += qq[j];
		if (i < n)
			qu[i + 1].push_back({ j - 1, -qq[j] });
	}
	build(m + 1);
	for (int i = 1; i <= n; i++) {
		for (auto &e : qu[i]) {
			int j = e.first, p = e.second;
			update_s(0, j, p);
		}
		sort(qu[i].begin(), qu[i].end());
		for (auto &e : qu[i]) {
			int j = e.first;
			update_a(j + 1, m, query(j));
		}
	}
	cout << s + query(m) << '\n';
	return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…