Submission #981579

#	Time	Username	Problem	Language	Result	Execution time	Memory
981579		josanneo22	Examination (JOI19_examination)	C++17	100 / 100	1446 ms	12124 KiB

examination

#pragma GCC optimize("O3")

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int nax = 100005;
const int BLOCK = 317;

struct query {
	int a, b, c, id;
	bool operator < (const query& o) const {
		int F = a / BLOCK;
		int S = o.a / BLOCK;
		if (F == S) return b < o.b;
		return F < S;
	}
};

#define low(x) x & -x
struct fenw {
	vector<i64> T;
	int _N;

	fenw(int N) {
		_N = N;
		T.assign(_N + 500, 0);
	}
	void update(int p, int x) {
		int P = p;
		while (P <= _N) {
			T[P] += x;
			P += low(P);
		}
	}
	int query(int x) {
		int P = x, res = 0;
		while (P >= 1) {
			res += T[P];
			P -= low(P);
		}
		return res;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

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

	vector<int> A(N), B(N), C(N), CC(N);
	vector<pair<int, int>> AA(N), BB(N);

	for (int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
		AA[i] = make_pair(A[i], i);
		BB[i] = make_pair(B[i], i);
		CC[i] = A[i] + B[i];
		C[i] = A[i] + B[i];
	}

	sort(AA.begin(), AA.end());
	sort(BB.begin(), BB.end());

	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	sort(C.begin(), C.end());

	for (int i = 0; i < N; i++) {
		AA[i].first = lower_bound(A.begin(), A.end(), AA[i].first) - A.begin();
		BB[i].first = lower_bound(B.begin(), B.end(), BB[i].first) - B.begin();
		CC[i] = lower_bound(C.begin(), C.end(), CC[i]) - C.begin();
	}

	vector<query> que(Q);
	for (int i = 0; i < Q; i++) {
		cin >> que[i].a >> que[i].b >> que[i].c;
		que[i].a = lower_bound(A.begin(), A.end(), que[i].a) - A.begin();
		que[i].b = lower_bound(B.begin(), B.end(), que[i].b) - B.begin();
		que[i].c = lower_bound(C.begin(), C.end(), que[i].c) - C.begin();
		que[i].id = i;
	}
	sort(que.begin(), que.end());

	vector<int> cnt(N), ans(Q);
	fenw fen(N);
	int L = N - 1, R = N - 1;
	for (int i = 0; i < Q; i++) {
		while (L >= que[i].a) {
			if (++cnt[AA[L].second] == 2)
				fen.update(CC[AA[L].second] + 1, +1);
			L--;
		}
		while (R >= que[i].b) {
			if (++cnt[BB[R].second] == 2)
				fen.update(CC[BB[R].second] + 1, +1);
			R--;
		}
		while (L + 1 < que[i].a) {
			L++;
			if (--cnt[AA[L].second] == 1)
				fen.update(CC[AA[L].second] + 1, -1);
		}
		while (R + 1 < que[i].b) {
			R++;
			if (--cnt[BB[R].second] == 1)
				fen.update(CC[BB[R].second] + 1, -1);
		}
		ans[que[i].id] = fen.query(N) - fen.query(que[i].c);
	}

	for (int i = 0; i < Q; i++) {
		cout << ans[i] << "\n";
	}
}

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