Submission #1273119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273119		kaiboy	단층 (JOI16_ho_t5)	C++20	100 / 100	59 ms	14136 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], n_;
long long st_x[N_ << 1], st_y[N_ << 1];

void pul_x(int i) {
	int l = i << 1, r = l ^ 1;
	st_x[i] = st_x[l] + st_x[r];
}

void pul_y(int i) {
	int l = i << 1, r = l ^ 1;
	st_y[i] = st_y[l] + st_y[r];
}

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 (n_ = 1; n_ <= n; n_ <<= 1)
		;
	for (int i = 0; i < n_; i++)
		st_x[i + n_] = st_y[i + n_] = 1;
	st_x[n_ - 1 + n_] = 1 - n_, st_y[n_] = 0;
	for (int i = n_ - 1; i; i--)
		pul_x(i), pul_y(i);
}

void update_x(int i, int x) {
	st_x[i += n_] += x, pull_x(i);
}

void update_y(int i, int y) {
	st_y[i += n_] += y, pull_y(i);
}

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

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

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--)
		if (dd[h] == 1) {
			int i = search_y(xx[h] - 1);
			if (i >= 0)
				update_x(i, ll[h] * 2);
		} else {
			int i = search_x(-xx[h]);
			if (i < n_)
				update_y(i, ll[h] * 2);
		}
	for (int i = n_ - 2; i >= 0; i--)
		st_x[i + n_] += st_x[i + 1 + n_];
	for (int i = 1; i < n_; i++)
		st_y[i + n_] += st_y[i - 1 + n_];
	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: 66 / 66