제출 #531988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531988		fhvirus	Examination (JOI19_examination)	C++17	100 / 100	344 ms	14036 KiB

examination

// Knapsack DP is harder than FFT.
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int, int> pii;
#define pb emplace_back
#define AI(x) begin(x),end(x)
#define ff first
#define ss second
#ifdef OWO
#define debug(args...) LKJ("\033[1;32m[ " + string(#args) + " ]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void OI(I a, I b) { while (a != b) cerr << *a << " \n"[(a = next(a)) == b]; }
#else
#define debug(...) 0
#define OI(...) 0
#endif

struct Lisan: vector<int> {
	void done() { sort(AI()); erase(unique(AI()), end()); }
	int operator () (const int& v) const { return lower_bound(AI(), v) - begin(); }
};
struct BIT {
	int n; vector<int> val;
	BIT (int _n): n(_n), val(_n + 1, 0) {}
	void modify(int p, int v) {
		for (; p > 0; p -= p & -p)
			val[p] += v;
	}
	int query(int p) {
		int r = 0;
		for (; p <= n; p += p & -p)
			r += val[p];
		return r;
	}
};
struct OBJ {
	int x, y, z, t;
	OBJ() = default;
	OBJ(int _x, int _y, int _z, int _t):
		x(_x), y(_y), z(_z), t(_t) {}
};
bool cmpX(const OBJ& a, const OBJ& b)
{ return a.x < b.x; }
bool cmpZ(const OBJ& a, const OBJ& b) {
	if (a.z != b.z) return a.z < b.z;
	return (a.t != 0) > (b.t != 0);
}

void solve(int lb, int rb, vector<OBJ>& objs, BIT& bit, vector<int>& ans) {
	if (lb + 1 >= rb) return;
	int mid = (lb + rb) / 2;
	solve(lb, mid, objs, bit, ans);
	solve(mid, rb, objs, bit, ans);

	int lp = mid - 1, rp = rb - 1;
	for (; lp >= lb; --lp) {
		while (rp >= mid and objs[rp].x >= objs[lp].x) {
			if (objs[rp].t == 0)
				bit.modify(objs[rp].y + 1, 1);
			--rp;
		}
		ans[objs[lp].t] += bit.query(objs[lp].y + 1);
	}
	for (++rp; rp < rb; ++rp)
		if (objs[rp].t == 0)
			bit.modify(objs[rp].y + 1, -1);
	inplace_merge(begin(objs) + lb, begin(objs) + mid, begin(objs) + rb, cmpX);
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N, Q; cin >> N >> Q;

	Lisan lisanX, lisanY;
	vector<OBJ> objs;
	for (int S, T, i = 0; i < N; ++i) {
		cin >> S >> T;
		objs.pb(S, T, S + T, 0);
		lisanX.pb(S);
		lisanY.pb(T);
	}
	for (int X, Y, Z, i = 1; i <= Q; ++i) {
		cin >> X >> Y >> Z;
		objs.pb(X, Y, Z, i);
		lisanX.pb(X);
		lisanY.pb(Y);
	}

	lisanX.done();
	lisanY.done();
	for (auto &[x, y, z, t]: objs) {
		x = lisanX(x);
		y = lisanY(y);
	}

	sort(AI(objs), cmpZ);

	for (auto &[x, y, z, t]: objs)
		debug(x, y, z, t);

	BIT bit(lisanY.size());
	vector<int> ans(Q + 1, 0);
	solve(0, objs.size(), objs, bit, ans);

	for (int i = 1; i <= Q; ++i)
		cout << ans[i] << '\n';

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'int main()':
examination.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
examination.cpp:101:3: note: in expansion of macro 'debug'
  101 |   debug(x, y, z, t);
      |   ^~~~~
examination.cpp:100:13: warning: unused structured binding declaration [-Wunused-variable]
  100 |  for (auto &[x, y, z, t]: objs)
      |             ^~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57