Submission #1241759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241759		wedonttalkanymore	Examination (JOI19_examination)	C++20	0 / 100	177 ms	22892 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long;

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 2e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ordered_set <pii> s1, s2;

struct item {
	int val, type, idx;
};
vector <item> comp;
int n, q;
int a[N], b[N];
int x[N], y[N], z[N];
int ans[N];

bool cmp(item a, item b) {
	return a.val < b.val;
	if (a.val == b.val) return a.type < b.type;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		comp.push_back({-(a[i] + b[i]), 0, i});
	}
	for (int i = 1; i <= q; i++) {
		cin >> x[i] >> y[i] >> z[i];
		z[i] = max(z[i], x[i] + y[i]);
		comp.push_back({-z[i], 1, i});
	}
	sort(comp.begin(), comp.end(), cmp);
//	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	int now = 0;
	for (auto val : comp) {
		int idx = val.idx;
		if (val.type == 0) {
			now++;
			s1.insert({a[idx], idx});
			s2.insert({b[idx], idx});
		}
		else {
			int t1 = s1.order_of_key({x[idx], 0LL});
			int t2 = s2.order_of_key({y[idx], 0LL});
			ans[idx] = now - t1 - t2;
		}
	}
	for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
	return 0;
}

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