Submission #127425

#	Time	Username	Problem	Language	Result	Execution time	Memory
127425		ainta	단층 (JOI16_ho_t5)	C++17	100 / 100	229 ms	29568 KiB

2016_ho_t5

#include<cstdio>
#include<algorithm>
#define SZ 262144
using namespace std;
long long R[SZ][2];
struct Tree {
	long long Mx[SZ + SZ], K[SZ + SZ];
	void UDT(int nd) {
		Mx[nd] = max(Mx[nd * 2], Mx[nd * 2 + 1]);
	}
	void init(int nd, int b, int e) {
		if (b == e) {
			Mx[nd] = b;
			return;
		}
		int m = (b + e) >> 1;
		init(nd * 2, b, m);
		init(nd * 2 + 1, m + 1, e);
		UDT(nd);
	}
	void Add2(int nd, long long x) {
		Mx[nd] += x;
		K[nd] += x;
	}
	void Spread(int nd) {
		Add2(nd*2, K[nd]);
		Add2(nd*2+1, K[nd]);
		K[nd] = 0;
	}
	void Add(int nd, int b, int e, int s, int l, int x) {
		if (s > l)return;
		if (s <= b && e <= l) {
			Add2(nd, x);
			return;
		}
		Spread(nd);
		int m = (b + e) >> 1;
		if (s <= m)Add(nd*2, b, m, s, l, x);
		if (l > m)Add(nd * 2 + 1, m + 1, e, s, l, x);
		UDT(nd);
	}
	int First(int nd, int b, int e, long long K) {
		if (Mx[nd] < K)return e + 1;
		if (b == e)return b;
		Spread(nd);
		int m = (b + e) >> 1;
		if (Mx[nd * 2] >= K)return First(nd * 2, b, m, K);
		return First(nd * 2 + 1, m + 1, e, K);
	}
	void Print(int nd, int b, int e, int ck) {
		if (b == e) {
			R[b][ck] = Mx[nd];
			return;
		}
		Spread(nd);
		int m = (b + e) >> 1;
		Print(nd * 2, b, m, ck);
		Print(nd * 2 + 1, m + 1, e, ck);
	}
}XMY, XPY;
int n, Q;
struct AA {
	int x, ck, l;
}U[SZ];
int main() {
	int i;
	scanf("%d%d", &n, &Q);
	XMY.init(1, 0, n - 1);
	XPY.init(1, 0, n - 1);
	for (i = 1; i <= Q; i++)scanf("%d%d%d", &U[i].x, &U[i].ck, &U[i].l);
	for (i = Q; i >= 1; i--) {
		int x, ck, l;
		x = U[i].x, ck = U[i].ck, l = U[i].l;
		if (ck == 1) {
			//x--;
			int t = XMY.First(1, 0, n - 1, x);
			XPY.Add(1, 0, n - 1, 0, t - 1, -2*l);
		}
		else {
			int t = XPY.First(1, 0, n - 1, x);
			XMY.Add(1, 0, n - 1, t, n - 1, 2*l);
		}
	}
	XMY.Print(1, 0, n - 1, 0);
	XPY.Print(1, 0, n - 1, 1);
	for (i = 0; i < n; i++)printf("%lld\n", -(R[i][1] - R[i][0]) / 2);
}

Compilation message (stderr)

2016_ho_t5.cpp: In function 'int main()':
2016_ho_t5.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
2016_ho_t5.cpp:70:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= Q; i++)scanf("%d%d%d", &U[i].x, &U[i].ck, &U[i].l);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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