Submission #206764

#	Time	Username	Problem	Language	Result	Execution time	Memory
206764		Neklixx	Examination (JOI19_examination)	C++14	100 / 100	2511 ms	374376 KiB

examination

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define sh cin.tie(0); cin.sync_with_stdio(0); cout.tie(0);
#define FILE freopen("test.in", "r", stdin);
#define vprint(v) for (int ii = 0; ii < v.size(); ii++){cout << v[ii] << " ";}
#define debugv(v) if (v.size() != 0) {cout << "[ "; for (int __ = 0; __ < (int)(v.size()) - 1; __++){cout << v[__] << ", ";} cout << v[(int)(v.size()) - 1] << " ]" << endl;} else {cout << "[]" << endl;}
#define debug cout << "-----------------------------------------------" << endl;
#define print1(a) cout << "{ " << a << " }" << endl;
#define print2(a, b) cout << "{ " << a << ", " << b << " }" << endl;
#define print3(a, b, c) cout << "{ " << a << ", " << b << ", " << c << " }" << endl;
#define print4(a, b, c, d) cout << "{ " << a << ", " << b << ", " << c << ", " << d << " }" << endl;
using namespace std;
//#define int long long
const int INF = 2e9 + 228;
const int MAXN = 1e5 + 228;
vector<pair<pair<int, int>, int>> a;
vector<pair<int, int>> t[MAXN * 4];

vector<vector<int>> t1[MAXN * 4];

void build1(int l, int r, int v, int id) {
	for (int i = l; i <= r; i++) {
		t1[id][v].pb(t[id][i].S);
	}
	sort(all(t1[id][v]));
	if (l == r) {
		return;
	}
	int mid = (l + r) / 2;
	build1(l, mid, v * 2, id);
	build1(mid + 1, r, v * 2 + 1, id);
}

void build(int l, int r, int v) {
	for (int i = l; i <= r; i++) {
		t[v].pb({a[i].F.S, a[i].S});
	}
	sort(all(t[v]));
	t1[v].resize(4 * t[v].size());
	build1(0, t[v].size() - 1, 1, v);
	if (l == r) {
		return;
	}
	int mid = (l + r) / 2;
	build(l, mid, 2 * v);
	build(mid + 1, r, v * 2 + 1);
}

int get1(int v, int l, int r, int tl, int tr, int z, int v1) {
	if (tl > tr)
		return 0;
	if (tl == l && tr == r) {
		int id = lower_bound(all(t1[v1][v]), z) - t1[v1][v].begin();
		return t1[v1][v].size() - id;
	}
	int mid = (l + r) / 2;
	return 	get1(v * 2, l, mid, tl, min(tr, mid), z, v1) + 
			get1(v * 2 + 1, mid + 1, r, max(tl, mid + 1), tr, z, v1);
}

int get(int v, int l, int r, int tl, int tr, int y, int z) {
	if (tl > tr)
		return 0;
	if (tl == l && tr == r) {
		int id = lower_bound(all(t[v]), mp(y, -INF)) - t[v].begin();
		return get1(1, 0, t[v].size() - 1, id, t[v].size() - 1, z, v);
	}
	int mid = (l + r) / 2;
	return 	get(v * 2, l, mid, tl, min(tr, mid), y, z) + 
			get(v * 2 + 1, mid + 1, r, max(tl, mid + 1), tr, y, z);
}

signed main()
{
#ifdef LOCAL
    FILE;
#endif
    sh;
	int n;
	cin >> n;
	int q;
	cin >> q;
	//print1("sorted");
	for (int i = 0; i < n; i++) {
		int aa, bb;
		cin >> aa >> bb;
		a.pb({{aa, bb}, aa + bb});
	}
	sort(all(a));
	build(0, n - 1, 1);
	//print1("built");
	for (int _ = 0; _ < q; _++) {
		int x, y, z;
		cin >> x >> y >> z;
		int id = lower_bound(all(a), mp(mp(x, -INF), -INF)) - a.begin();
		int now = get(1, 0, n - 1, id, n - 1, y, z);
		cout << now << endl;
	}
    return 0;
}

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