Submission #1267611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267611		trvhung	Examination (JOI19_examination)	C++20	100 / 100	286 ms	100224 KiB

examination

#include <bits/stdc++.h>
// #include <ext/rope>
// #include <ext/pb_ds/assoc_container.hpp>

// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

// #define   ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define            ll long long
#define           ull unsigned long long
#define            ld long double
#define            pb push_back
#define  bit(mask, i) ((mask >> i) & 1)
#define            el '\n'
#define             F first
#define             S second

template <class X, class Y> bool maximize(X &x, const Y &y) { return (x < y ? x = y, 1 : 0); }
template <class X, class Y> bool minimize(X &x, const Y &y) { return (x > y ? x = y, 1 : 0); }

const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int MULTI = 0;
const ld eps = 1e-9;
const int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // R D L U
const int ddx[4] = {-1, 1, 1, -1}, ddy[4] = {1, 1, -1, -1}; // UR DR DL UL
const char cx[4] = {'R', 'D', 'L', 'U'};
const ll base = 31;
const int nMOD = 2;
const ll mods[] = {(ll)1e9 + 10777, (ll)1e9 + 19777, (ll)1e9 + 3, (ll)1e9 + 3777};

const int N = 1e5 + 5;
int n, q, curId = 1, sum[N], ps[N], pz[N], res[N];
pair<int, int> s[N];
vector<int> comp;

struct crit {
	int x, y, z, id;
} c[N];

struct query {
	int x, id;
	query(int _x = 0, int _id = 0) : x(_x), id(_id) {}
};

vector<query> queries[N];

void compressSum() {
	for (int i = 1; i <= n; ++i)
		comp.push_back(s[i].F + s[i].S);
	for (int i = 1; i <= q; ++i)
		comp.push_back(c[i].z);

	sort(comp.begin(), comp.end());
	comp.resize(unique(comp.begin(), comp.end()) - comp.begin());

	for (int i = 1; i <= n; ++i) 
		sum[i] = lower_bound(comp.begin(), comp.end(), s[i].F + s[i].S) - comp.begin() + 1;
	for (int i = 1; i <= q; ++i)
		pz[i] = lower_bound(comp.begin(), comp.end(), c[i].z) - comp.begin() + 1;
}

void compressS() {
	comp.clear();
	for (int i = 1; i <= n; ++i)
		comp.push_back(s[i].F);
	for (int i = 1; i <= n; ++i)
		for (auto qr: queries[i])
			comp.push_back(qr.x);

	sort(comp.begin(), comp.end());
	comp.resize(unique(comp.begin(), comp.end()) - comp.begin());

	for (int i = 1; i <= n; ++i)
		ps[i] = lower_bound(comp.begin(), comp.end(), s[i].F) - comp.begin() + 1;
	for (int i = 1; i <= n; ++i)
		for (auto &qr: queries[i]) 
			qr.x = lower_bound(comp.begin(), comp.end(), qr.x) - comp.begin() + 1;
}

struct node {
	int idLeft, idRight;
	vector<int> vec;
	vector<int> freq = {0};
} st[8 * N];

struct WaveletTree {
	int lo, hi;

	void build(int id, int l, int r) {
		if (l == r) return;

		int mid = (l + r) >> 1;
		vector<int> left, right;

		for (int x: st[id].vec)
			if (x <= mid) {
				left.push_back(x);
				st[id].freq.push_back(st[id].freq.back() + 1);
			} else {
				right.push_back(x);
				st[id].freq.push_back(st[id].freq.back());
			}

		st[id].idLeft = ++curId;
		st[curId].vec = left;
		build(curId, l, mid);

		st[id].idRight = ++curId;
		st[curId].vec = right;
		build(curId, mid + 1, r);
	}

	int lessThanK(int id, int l, int r, int u, int v, int k) {
		if (u > v || k <= l) return 0;
		if (r < k) return v - u + 1;

		int LtCount = st[id].freq[u - 1], RtCount = st[id].freq[v];
		int mid = (l + r) >> 1;

		return lessThanK(st[id].idLeft, l, mid, LtCount + 1, RtCount, k) + lessThanK(st[id].idRight, mid + 1, r, u - LtCount, v - RtCount, k);
	}

	int get(int l, int r, int k) {
		return r - l + 1 - lessThanK(1, lo, hi, l, r, k);
	}

	void prep() {
		for (int i = 1; i <= n; ++i)
			st[1].vec.push_back(sum[i]);

		lo = *min_element(sum + 1, sum + 1 + n);
		hi = *max_element(sum + 1, sum + 1 + n);

		build(1, lo, hi);
	}
} wt;

struct BIT {
	int bit[N << 1];

	void update(int id) {
		for (; id > 0; id -= id & -id)
			bit[id]++;
	}

	int get(int id) {
		int res = 0;
		for (; id <= n + q; id += id & -id)
			res += bit[id];
		return res;
	}
} BIT;

void solve() {
	cin >> n >> q;
	for (int i = 1; i <= n; ++i)
		cin >> s[i].F >> s[i].S;
	for (int i = 1; i <= q; ++i) {
		cin >> c[i].x >> c[i].y >> c[i].z;
		c[i].id = i;
 	}

	sort(s + 1, s + 1 + n, [&](pair<int, int> A, pair<int, int> B){
		return A.S < B.S;
	});
	sort(c + 1, c + 1 + q, [&](crit A, crit B){
		return A.y < B.y;
	});

	compressSum();
	wt.prep();

	int cur = n + 1;
	for (int i = q; i >= 1; --i) {
		while (cur > 1 && s[cur - 1].S >= c[i].y) cur--;
		
		int l = cur, r = n, p = n + 1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (s[mid].S >= c[i].z - c[i].x) {
				p = mid;
				r = mid - 1;
			} else l = mid + 1;
		}

		if (p <= n) queries[p].push_back(query(c[i].x, c[i].id));
		if (p > cur) res[c[i].id] = wt.get(cur, p - 1, pz[i]);
	}

	compressS();

	for (int i = n; i >= 1; --i) {
		BIT.update(ps[i]);
		for (auto &qr: queries[i])
			res[qr.id] += BIT.get(qr.x);
	}

	for (int i = 1; i <= q; ++i)
		cout << res[i] << el;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if (!MULTI) solve();
    else {
        int test; cin >> test;
        while (test--) solve();
    }
    
    return 0;
}

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