제출 #1031857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031857		juicy	Examination (JOI19_examination)	C++17	22 / 100	114 ms	17260 KiB

examination

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5;

struct Fenwick {
	int s[N];

	void upd(int i) {
		for (; i; i -= i & -i) {
			++s[i];
		}
	} 

	int qry(int i) {
		int res = 0;
		for (; i < N; i += i & -i) {
			res += s[i];
		}
		return res;
	}
} ft[2];

int n, q;
int res[N];
array<int, 2> pt[N];

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

	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> pt[i][0] >> pt[i][1];
	}	
	vector<array<int, 4>> Queries;
	array<vector<int>, 2> comp;
	for (int i = 1; i <= q; ++i) {
		int x, y, z; cin >> x >> y >> z;
		comp[0].push_back(y);
		comp[1].push_back(z);
		if (y < z - x) {
			Queries.push_back({x, z, i, 1});
			Queries.push_back({z - y, z, -i, 1});
			Queries.push_back({z - y, y, i, 0});
		} else {
			Queries.push_back({x, y, i, 0});
		}
	}	
	sort(Queries.rbegin(), Queries.rend());
	sort(pt + 1, pt + n + 1);
	for (int i = 1; i <= n; ++i) {
		comp[0].push_back(pt[i][1]);
		comp[1].push_back(pt[i][0] + pt[i][1]);
	}
	for (auto it : {0, 1}) {
		sort(comp[it].begin(), comp[it].end());
		comp[it].erase(unique(comp[it].begin(), comp[it].end()), comp[it].end());
	}
	auto getID = [](vector<int> &comp, int val) {
		return lower_bound(comp.begin(), comp.end(), val) - comp.begin() + 1;
	};
	int j = n;
	for (auto [x, y, id, type] : Queries) {
		while (j > 0 && pt[j][0] >= x) {
			int p = getID(comp[0], pt[j][1]);
			ft[0].upd(p);
			p = getID(comp[1], pt[j][0] + pt[j][1]);
			ft[1].upd(p);
			--j;
		}
		y = getID(comp[type], y);
		if (id > 0) {
			res[id] += ft[type].qry(y);
		} else {
			res[-id] -= ft[type].qry(y);
		}
	}
	for (int i = 1; i <= q; ++i) { 
		cout << res[i] << "\n";
	}
	return 0;
}

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