Submission #732952

#	Time	Username	Problem	Language	Result	Execution time	Memory
732952		flappybird	단층 (JOI16_ho_t5)	C++17	100 / 100	193 ms	14648 KiB

2016_ho_t5

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
struct fenwick {
	vector<ll> tree;
	int N;
	fenwick(int N = 0) :N(N) { tree.resize(N + 1); }
	void upd(int i, ll x) { while (i <= N) { tree[i] += x, i += i & -i; } }
	ll sum(int i) { ll ans = 0; while (i) { ans += tree[i], i -= i & -i; } return ans; }
}Xfen, Yfen;
ll P[MAX];
int D[MAX];
ll L[MAX];
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	int i;
	Xfen = Yfen = fenwick(N);
	for (i = 1; i <= N; i++) Xfen.upd(i, 1);
	for (i = 1; i <= N; i++) Yfen.upd(i, 1);
	for (i = 1; i <= Q; i++) cin >> P[i] >> D[i] >> L[i];
	for (i = Q; i >= 1; i--) {
		if (D[i] == 1) {
			int l, r;
			l = 0;
			r = N + 1;
			while (r - l > 1) {
				int m = l + r >> 1;
				if (Xfen.sum(m) <= P[i]) l = m;
				else r = m;
			}
			Yfen.upd(1, -2 * L[i]);
			Yfen.upd(l + 1, 2 * L[i]);
		}
		else {
			int l, r;
			l = 0;
			r = N + 1;
			while (r - l > 1) {
				int m = l + r >> 1;
				if (Yfen.sum(m) <= P[i]) l = m;
				else r = m;
			}
			Xfen.upd(r, 2 * L[i]);
		}
	}
	for (i = 1; i <= N; i++) cout << (Xfen.sum(i) - Yfen.sum(i)) / 2 << ln;
}

Compilation message (stderr)

2016_ho_t5.cpp: In function 'int main()':
2016_ho_t5.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int m = l + r >> 1;
      |             ~~^~~
2016_ho_t5.cpp:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     int m = l + r >> 1;
      |             ~~^~~

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