Submission #1273083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273083		kaiboy	단층 (JOI16_ho_t5)	C++20	34 / 100	2095 ms	14872 KiB

2016_ho_t5

#include <algorithm>
#include <iostream>

using namespace std;

const int  M = 200000;
const int N_ = 1 << 18;

int xx[M], dd[M], ll[M], h_, n_;
long long st_x[N_ << 1], st_y[N_ << 1], lz_x[N_], lz_y[N_];

void put_x(int i, long long x) {
	st_x[i] += x;
	if (i < n_)
		lz_x[i] += x;
}

void put_y(int i, long long y) {
	st_y[i] += y;
	if (i < n_)
		lz_y[i] += y;
}

void pus_x(int i) {
	if (lz_x[i]) {
		int l = i << 1, r = l ^ 1;
		put_x(l, lz_x[i]);
		put_x(r, lz_x[i]);
		lz_x[i] = 0;
	}
}

void pus_y(int i) {
	if (lz_y[i]) {
		int l = i << 1, r = l ^ 1;
		put_y(l, lz_y[i]);
		put_y(r, lz_y[i]);
		lz_y[i] = 0;
	}
}

void pul_x(int i) {
	if (!lz_x[i]) {
		int l = i << 1, r = l ^ 1;
		st_x[i] = min(st_x[l], st_x[r]);
	}
}

void pul_y(int i) {
	if (!lz_y[i]) {
		int l = i << 1, r = l ^ 1;
		st_y[i] = min(st_y[l], st_y[r]);
	}
}

void push_x(int i) {
	for (int h = h_; h; h--)
		pus_x(i >> h);
}

void push_y(int i) {
	for (int h = h_; h; h--)
		pus_y(i >> h);
}

void pull_x(int i) {
	while (i >>= 1)
		pul_x(i);
}

void pull_y(int i) {
	while (i >>= 1)
		pul_y(i);
}

void build(int n) {
	for (h_ = 0, n_ = 1; n_ <= n; h_++, n_ <<= 1)
		;
	for (int i = 0; i < n_; i++)
		st_x[i + n_] = -i, st_y[i + n_] = i, lz_x[i] = lz_y[i] = 0;
	for (int i = n_ - 1; i; i--)
		pul_x(i), pul_y(i);
}

void update_x(int l, int r, int x) {
	int l_ = l += n_, r_ = r += n_;
	push_x(l_), push_x(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			put_x(l++, x);
		if (!(r & 1))
			put_x(r--, x);
	}
	pull_x(l_), pull_x(r_);
}

void update_y(int l, int r, int y) {
	int l_ = l += n_, r_ = r += n_;
	push_y(l_), push_y(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if (l & 1)
			put_y(l++, y);
		if (!(r & 1))
			put_y(r--, y);
	}
	pull_y(l_), pull_y(r_);
}

int search_x(int x) {
	if (st_x[1] > x)
		return n_;
	int i = 1;
	while (i < n_) {
		pus_x(i);
		if (st_x[i <<= 1] > x)
			i ^= 1;
	}
	return i - n_;
}

int search_y(int y) {
	if (st_y[1] > y)
		return -1;
	int i = 1;
	while (i < n_) {
		pus_y(i);
		if (st_y[(i <<= 1) ^ 1] <= y)
			i ^= 1;
	}
	return i - n_;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	for (int h = 0; h < m; h++)
		cin >> xx[h] >> dd[h] >> ll[h];
	build(n);
	for (int h = m - 1; h >= 0; h--) {
		for (int i = 1; i < n_; i++)
			pus_x(i), pus_y(i);
		if (dd[h] == 1) {
			int i = search_y(xx[h] - 1);
			if (i >= 0)
				update_x(0, i, ll[h] * 2);
		} else {
			int i = search_x(-xx[h]);
			if (i < n_)
				update_y(i, n_ - 1, ll[h] * 2);
		}
	}
	for (int i = 1; i < n_; i++)
		pus_x(i), pus_y(i);
	for (int i = 0; i < n; i++)
		cout << (st_x[i + n_] + st_y[i + n_]) / 2 << '\n';
	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 16 / 16
• Subtask 3: 0 / 66