Submission #518571

#	Time	Username	Problem	Language	Result	Execution time	Memory
518571		starchan	Examination (JOI19_examination)	C++17	100 / 100	194 ms	22364 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF 1e17
#define zero (int)0
#define MX (int)3e5+5
#define LMX (int)5e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
const int mod = 1e9+7; //may change to that 99.. number.
struct segment_tree
{
	vector<int> tree;
	void init()
	{
		tree.assign(LMX, 0);
		return;
	}
	void upd(int x, int id, int l, int r)
	{
		int m = (l+r)/2;
		if(l == r)
		{
			tree[id]++;
			return;
		}
		if(x <= m)
			upd(x, 2*id, l, m);
		else
			upd(x, 2*id+1, m+1, r);
		tree[id] = tree[2*id]+tree[2*id+1];
		return;
	}
	int sum(int ql, int qr, int id, int l, int r)
	{
		int m = (l+r)/2;
		if(l > qr || ql > r)
			return 0;
		if(ql <= l && r <= qr)
			return tree[id];
		int sum1 = sum(ql, qr, 2*id, l, m);
		int sum2 = sum(ql, qr, 2*id+1, m+1, r);
		return sum1+sum2;
	}
};
vector<int> solve(vector<in> queries, vector<int> a, int n, int q)
{
	segment_tree work;
	work.init();
	vector<in> ok(n+2);
	ok[n+1] = {INF, INF}; 
	vector<pair<in, int>> quer(q);
	for(int i = 0; i < q; i++)
	{
		quer[i].f.f = queries[i].s;
		quer[i].f.s = queries[i].f;
		quer[i].s = i;
	}
	for(int i = 1; i <= n; i++)
		ok[i] = {a[i], i};
	ok[0] = {-INF, -1};
	int curr = 1;
	sort(ok.begin(), ok.end());
	vector<int> ans(q);
	sort(quer.begin(), quer.end());
	for(int i = 0; i < q; i++)
	{		
		if(quer[i].f.s == 0)
		{
			ans[quer[i].s] = 0;
			continue;
		}
		while(ok[curr].f < quer[i].f.f)
		{
			work.upd(ok[curr].s, 1, 1, n);
			curr++;
		}
		ans[quer[i].s] = work.sum(1, quer[i].f.s, 1, 1, n);
	}
	return ans;
}
signed main()
{
	fast();
	int n, q;
	cin >> n >> q;
	vector<pair<int, in>> values(n+1);
	vector<int> a(n+1);
	vector<int> b(n+1);
	vector<int> c(n+1);
	for(int i = 1; i <= n; i++)
	{
		int a, b;
		cin >> a >> b;
		values[i] = {-a-b, {a, b}};
	}
	values[0] = {-INF, {0, 0}};
	sort(values.begin(), values.end());
	for(int i = 1; i <= n; i++)
	{
		c[i] = -values[i].f;
		a[i] = values[i].s.f;
		b[i] = values[i].s.s;
	}
	vector<int> oh(q);
	vector<in> queries_a(q);
	vector<in> queries_b(q);
	for(int i = 0; i < q; i++)
	{
		int z;
		cin >> queries_a[i].s >> queries_b[i].s >> z;
		z = max(z, queries_a[i].s+queries_b[i].s);
		int l = 1;
		int r = n+1;
		while(l < r)
		{
			int m = (l+r)/2;
			if(c[m] < z)
				r = m;
			else
				l = m+1;
		}
		l--;
		oh[i] = queries_a[i].f = queries_b[i].f = l;
	}
	vector<int> ans_a = solve(queries_a, a, n, q);
	vector<int> ans_b = solve(queries_b, b, n, q);
	for(int i = 0; i < q; i++)
		cout << oh[i]-ans_a[i]-ans_b[i] << "\n";
	return 0;
}

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