제출 #1327815

#제출 시각아이디문제언어결과실행 시간메모리
1327815crispxxExamination (JOI19_examination)C++20
100 / 100
129 ms7596 KiB
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct fenw {
	int n; vector<int> bit;
	
	fenw(int n) : n(n), bit(n + 1) {}
	
	void update(int i, int x) {
		for(i++; i <= n; i += i & -i) bit[i] += x;
	}
	
	int get(int i) {
		int res = 0;
		for(i++; i >= 1; i -= i & -i) res += bit[i];
		return res;
	}
	
	int get(int l, int r) {
		return get(r) - get(l - 1);
	}
};

void solve() {
	int n, q; cin >> n >> q;
	
	vector<int> b;
	
	vector<array<int, 2>> a1;
	vector<array<int, 3>> a2;
	
	for(int i = 0; i < n; i++) {
		int s, t; cin >> s >> t;
		
		a1.push_back({s, t});
		a2.push_back({s + t, s, t});
		
		b.push_back(s);
		b.push_back(t);
	}
	
	vector<array<int, 4>> q1, q2;
	
	for(int i = 0; i < q; i++) {
		int x, y, z; cin >> x >> y >> z;
		
		if(x + y >= z) {
			q1.push_back({x, y, z, i});
		} else {
			q2.push_back({z, x, y, i});
		}
	}
	
	sort(a1.begin(), a1.end(), greater<>());
	sort(a2.begin(), a2.end(), greater<>());
	
	sort(q1.begin(), q1.end(), greater<>());
	sort(q2.begin(), q2.end(), greater<>());
	
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	
	auto idx = [&](int x) {
		return lower_bound(b.begin(), b.end(), x) - b.begin();
	};
	
	int m = b.size();
	
	vector<int> ans(q);
	
	{ // x + y >= z
		fenw fn(m + 1);
		
		for(int i = 0, j = 0; i < (int)q1.size(); i++) {
			while(j < (int)a1.size() && a1[j][0] >= q1[i][0]) {
				fn.update( idx(a1[j][1]), 1 );
				j++;
			}
			
			ans[q1[i][3]] = fn.get( idx(q1[i][1]), m );
		}
	}
	
	{ // x + y < z
		fenw fnx(m + 1), fny(m + 1);
		
		for(int i = 0, j = 0; i < (int)q2.size(); i++) {
			while(j < (int)a2.size() && a2[j][0] >= q2[i][0]) {
				fnx.update( idx(a2[j][1]), 1 );
				fny.update( idx(a2[j][2]), 1 );
				j++;
			}
			
			ans[q2[i][3]] += fnx.get( idx(q2[i][1]) - 1 );
			ans[q2[i][3]] += fny.get( idx(q2[i][2]) - 1 );
			
			ans[q2[i][3]] = j - ans[q2[i][3]];
		}
	}
	
	for(auto &x : ans) cout << x << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...