Submission #630304

#	Time	Username	Problem	Language	Result	Execution time	Memory
630304		pooyashams	Examination (JOI19_examination)	C++14	100 / 100	1630 ms	137916 KiB

examination

// this code is almost n.sq.log don't trust it
#pragma GCC optimize("Ofast")
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define endl '\n'
#define X first
#define Y second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 2e5+10;
const int bl = 320;
const int sq = 400;
//const int bl = 2;
//const int sq = 10000;

pii arr[maxn];

struct qr
{
	int x, y, z, i;
} qrs[maxn];
int perm[maxn];

vector<int> qsts[maxn];
int ans[maxn];

inline bool cmpsum(pii a, pii b)
{
	return a.X+a.Y > b.X+b.Y;
}

inline bool cmpq(int i, int j)
{
	return qrs[i].x > qrs[j].x;
}

pii trr[maxn];
int tbr[maxn];

inline int get_gcnt(int s, int b)
{
	return upper_bound(tbr, tbr+s, b, greater<int>()) - tbr;
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q; cin >> n >> q;
	for(int i = 0; i < n; i++)
	{
		cin >> arr[i].X >> arr[i].Y;
	}
	sort(arr, arr+n, cmpsum);
	//cerr << n << endl;
	//for(int i = 0; i < n; i++)
	//	cerr << arr[i].X << " " << arr[i].Y << endl;
	//cerr << "---" << endl;
	for(int i = 0; i < q; i++)
	{
		cin >> qrs[i].x >> qrs[i].y >> qrs[i].z;
		qrs[i].i = i;
	}
	iota(perm, perm+q, 0);
	sort(perm, perm+q, cmpq);
	for(int idx = 0; idx < q; idx++)
	{
		int i = perm[idx];
		for(int j = 0; j*bl < n; j++)
		{
			int e = min(n, j*bl+bl);
			if( (arr[e-1].X + arr[e-1].Y) >= qrs[i].z)
			{
				qsts[j].push_back(i);
			}
			else
			{
				for(int k = j*bl; k < e; k++)
				{
					if(arr[k].X >= qrs[i].x and arr[k].Y >= qrs[i].y and (arr[k].X+arr[k].Y) >= qrs[i].z)
						ans[i]++;
				}
				break;
			}
		}
	}
	for(int i = 0; i*bl < n; i++)
	{
		int s = i*bl;
		int e = min(n, i*bl+bl);
		int sz = e-s;
		for(int j = s; j < e; j++)
			trr[j-s] = arr[j];
		sort(trr, trr+sz, greater<pii>());
		//sort(qsts[i].begin(), qsts[i].end(), cmpq);
		int p = 0;
		int qs = qsts[i].size();
		for(int j = 0; j < sz; j++)
		{
			while(p < qs and qrs[qsts[i][p]].x > trr[j].X)
			{
				ans[qsts[i][p]] += get_gcnt(j, qrs[qsts[i][p]].y);
				p++;
			}
			{
				tbr[j] = trr[j].Y;
				int x = j;
				while(x > 0 and tbr[x] > tbr[x-1])
				{
					swap(tbr[x], tbr[x-1]);
					x--;
				}
			}
		}
		while(p < qs)
		{
			ans[qsts[i][p]] += get_gcnt(sz, qrs[qsts[i][p]].y);
			p++;
		}
	}
	for(int i = 0; i < q; i++)
		cout << ans[i] << endl;
	return 0;
}

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