제출 #1366543

#제출 시각아이디문제언어결과실행 시간메모리
1366543kaiboyExamination (JOI19_examination)C++20
100 / 100
97 ms6884 KiB
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100000;
const int Q = 100000;

int aa[N], bb[N], cc[N], iia[N], iib[N], iic[N], hha[N], hhb[N];
int aa_[Q], bb_[Q], cc_[Q], zz[Q], xx[Q], fta[N], ftb[N];

void update(int *ft, int i, int n, int a) {
	for ( ; i < n; i |= i + 1)
		ft[i] += a;
}

int query(int *ft, int i) {
	int a = 0;
	for ( ; i >= 0; i &= i + 1, i--)
		a += ft[i];
	return a;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, q; cin >> n >> q;
	for (int i = 0; i < n; i++)
		cin >> aa[i] >> bb[i], cc[i] = aa[i] + bb[i], iia[i] = iib[i] = iic[i] = i;
	sort(iia, iia + n, [] (int i, int j) { return aa[i] < aa[j]; });
	sort(iib, iib + n, [] (int i, int j) { return bb[i] < bb[j]; });
	sort(iic, iic + n, [] (int i, int j) { return cc[i] > cc[j]; });
	for (int h = 0; h < n; h++)
		hha[iia[h]] = hhb[iib[h]] = h;
	for (int z = 0; z < q; z++)
		cin >> aa_[z] >> bb_[z] >> cc_[z], cc_[z] = max(cc_[z], aa_[z] + bb_[z]), zz[z] = z;
	sort(zz, zz + q, [] (int z0, int z1) { return cc_[z0] > cc_[z1]; });
	for (int y = 0, h = 0; y < q; y++) {
		int z = zz[y], a_ = aa_[z], b_ = bb_[z], c_ = cc_[z];
		for (int i; h < n && cc[i = iic[h]] >= c_; h++)
			update(fta, hha[i], n, 1), update(ftb, hhb[i], n, 1);
		int lower = -1, upper = n;
		while (upper - lower > 1) {
			int h = lower + upper >> 1;
			if (aa[iia[h]] < a_)
				lower = h;
			else
				upper = h;
		}
		int ha = lower; lower = -1, upper = n;
		while (upper - lower > 1) {
			int h = lower + upper >> 1;
			if (bb[iib[h]] < b_)
				lower = h;
			else
				upper = h;
		}
		int hb = lower;
		xx[z] = h - query(fta, ha) - query(ftb, hb);
	}
	for (int z = 0; z < q; z++)
		cout << xx[z] << '\n';
	return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…