Submission #411577

#	Time	Username	Problem	Language	Result	Execution time	Memory
411577		ngpin04	Examination (JOI19_examination)	C++14	100 / 100	1034 ms	57264 KiB

examination

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e5 + 5; 

struct BIT2D {
	int n;
	vector <int> sz;
	vector <int> valx;
	vector <vector <int>> valy; 
	vector <vector <int>> bit;

	void addx(int x) {
		valx.push_back(x);
	}

	void buildx() {
		sort(valx.begin(), valx.end());
		valx.resize(unique(valx.begin(), valx.end()) - valx.begin());
		n = valx.size();
		valy.resize(n + 1);
		sz.resize(n + 1);
		bit.resize(n + 1);
	}

	void add(int x, int y) {
		x = lower_bound(valx.begin(), valx.end(), x) - valx.begin() + 1;
		for (int i = x; i <= n; i += i & -i) 
			valy[i].push_back(y);

		for (int i = x; i > 0; i -= i & -i)
			valy[i].push_back(y);
	}

	void buildy() {
		for (int i = 1; i <= n; i++) {
			sort(valy[i].begin(), valy[i].end());
			valy[i].resize(unique(valy[i].begin(), valy[i].end()) - valy[i].begin());
			sz[i] = valy[i].size();
			bit[i].resize(sz[i] + 1);			
		}
	}

	void update(int x, int y) {
		x = lower_bound(valx.begin(), valx.end(), x) - valx.begin() + 1;
		for (; x <= n; x += x & -x) {
			int st = lower_bound(valy[x].begin(), valy[x].end(), y) - valy[x].begin() + 1;
			for (int i = st; i <= sz[x]; i += i & -i) 
				bit[x][i]++;
		}
	}

	int getsum(int x, int y) {
		int res = 0;
		x = lower_bound(valx.begin(), valx.end(), x) - valx.begin() + 1;
		for (; x > 0; x -= x & -x) {
			int st = lower_bound(valy[x].begin(), valy[x].end(), y) - valy[x].begin() + 1;				
			for (int i = st; i > 0; i -= i & -i) 
				res += bit[x][i];
		}
		return res;
	}
};

pair <pair <int, int>, int> qr[N];
pair <int, int> a[N];

int ans[N];
int n,q;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	BIT2D bit;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].fi >> a[i].se;
		bit.addx(-a[i].fi);
	}

	for (int i = 1; i <= q; i++) {
		cin >> qr[i].fi.fi >> qr[i].fi.se >> qr[i].se;
		bit.addx(-qr[i].fi.fi);
	}
	bit.buildx();
	for (int i = 1; i <= q; i++) 
		bit.add(-qr[i].fi.fi, -qr[i].fi.se);

	for (int i = 1; i <= n; i++)
		bit.add(-a[i].fi, -a[i].se);
	
	bit.buildy();
	vector <int> id(q);
	iota(id.begin(), id.end(), 1);
	sort(id.begin(), id.end(), [](int i, int j) {
		return qr[i].se > qr[j].se;
	});

	sort(a + 1, a + n + 1, [](auto a, auto b) {
		return a.fi + a.se > b.fi + b.se;
	});

	int j = 1;
	for (int i : id) {
		while (j <= n && a[j].fi + a[j].se >= qr[i].se) {
			bit.update(-a[j].fi, -a[j].se);
			j++;
		}		
		ans[i] = bit.getsum(-qr[i].fi.fi, -qr[i].fi.se);
	}

	for (int i = 1; i <= q; i++)
		cout << ans[i] << "\n";
	return 0;
}

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