제출 #384310

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
384310		amoo_safar	Examination (JOI19_examination)	C++17	2 / 100	3052 ms	71120 KiB

examination

// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 998244353;
const int N = 1e5 + 10;
const int Inf = 2000000100;
const ll Log = 30;

typedef pair<int, int> pii;

struct Segment {
	int n = 0;
	vector<pii> V;
	vector<int> seg[N << 2];

	void Add(pii X){
		V.pb(X);
		return ;
	}
	void Build(int id, int L, int R){
		for(int i = L; i < R; i++) seg[id].pb(V[i].S);
		sort(all(seg[id]));
		if(L + 1 == R) return ;
		int mid = (L + R) >> 1;
		Build(id << 1, L, mid);
		Build(id<<1|1, mid, R);
	}
	int Get(int id, int l, int r, int lw, int hg, int L, int R){
		if(r <= L || R <= l) return 0;
		if(l <= L && R <= r){
			return lower_bound(all(seg[id]), hg + 1) - lower_bound(all(seg[id]), lw);
		}
		int mid = (L + R) >> 1;
		return Get(id << 1, l, r, lw, hg, L, mid) + Get(id << 1 | 1, l, r, lw, hg, mid, R);
	}
	int GetRect(int lx, int rx, int ly, int ry){ // [], []
		// lx = lower_bound(all(V), pii(lx, -Inf)) - V.begin();
		// rx = lower_bound(all(V), pii(rx, Inf)) - V.begin();
		int sm = 0;
		for(auto [x, y] : V)
			if(lx <= x && x <= rx && ly <= y && y <= ry) sm ++;
		return sm;

		return Get(1, lx, rx, ly, ry, 0, n);
	}
	void init(){
		n = V.size();
		sort(all(V));
		Build(1, 0, n);
	}
};
Segment SX, SY, XY;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, q;
	cin >> n >> q;
	int x, y;
	vector<int> U;
	for(int i = 0; i < n; i++){
		cin >> x >> y;
		SX.Add({x + y, x});
		SY.Add({x + y, y});
		XY.Add({x, y});
		U.pb(x + y);
	}
	sort(all(U));
	SX.init();
	SY.init();
	XY.init();

	int a, b, c;
	for(int i = 0; i < q; i++){
		cin >> a >> b >> c;
		if(a + b >= c){
			cout << XY.GetRect(a, Inf, b, Inf) << '\n';
			continue;
		}
		int und = lower_bound(all(U), c) - U.begin();
		int lf = SX.GetRect(c, Inf, 0, a - 1);
		int rt = SY.GetRect(c, Inf, 0, b - 1);
		cout << n - und - lf - rt << '\n';
	}
	return 0;
}
/*
5 1
1 2
2 3
3 4
1 5

*/

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