oj.uz

Submission #630301

# Submission time Handle Problem Language Result Execution time Memory
630301 2022-08-16T07:30:37 Z pooyashams Examination (JOI19_examination) C++14
100 / 100
 1603 ms 140476 KB 
#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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5040 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 10 ms 5288 KB Output is correct
9 Correct 9 ms 5332 KB Output is correct
10 Correct 8 ms 5276 KB Output is correct
11 Correct 9 ms 5368 KB Output is correct
12 Correct 8 ms 5204 KB Output is correct
13 Correct 7 ms 5416 KB Output is correct
14 Correct 8 ms 5436 KB Output is correct
15 Correct 7 ms 5428 KB Output is correct
16 Correct 5 ms 5460 KB Output is correct
17 Correct 6 ms 5304 KB Output is correct
18 Correct 5 ms 5180 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1120 ms 140172 KB Output is correct
2 Correct 1126 ms 140320 KB Output is correct
3 Correct 1125 ms 140280 KB Output is correct
4 Correct 909 ms 139548 KB Output is correct
5 Correct 689 ms 139540 KB Output is correct
6 Correct 812 ms 138956 KB Output is correct
7 Correct 1603 ms 140364 KB Output is correct
8 Correct 890 ms 140272 KB Output is correct
9 Correct 1083 ms 140096 KB Output is correct
10 Correct 485 ms 139440 KB Output is correct
11 Correct 634 ms 139452 KB Output is correct
12 Correct 393 ms 138412 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1120 ms 140172 KB Output is correct
2 Correct 1126 ms 140320 KB Output is correct
3 Correct 1125 ms 140280 KB Output is correct
4 Correct 909 ms 139548 KB Output is correct
5 Correct 689 ms 139540 KB Output is correct
6 Correct 812 ms 138956 KB Output is correct
7 Correct 1603 ms 140364 KB Output is correct
8 Correct 890 ms 140272 KB Output is correct
9 Correct 1083 ms 140096 KB Output is correct
10 Correct 485 ms 139440 KB Output is correct
11 Correct 634 ms 139452 KB Output is correct
12 Correct 393 ms 138412 KB Output is correct
13 Correct 751 ms 79928 KB Output is correct
14 Correct 1061 ms 119916 KB Output is correct
15 Correct 1118 ms 140476 KB Output is correct
16 Correct 742 ms 77308 KB Output is correct
17 Correct 543 ms 77352 KB Output is correct
18 Correct 912 ms 118564 KB Output is correct
19 Correct 798 ms 79876 KB Output is correct
20 Correct 946 ms 97728 KB Output is correct
21 Correct 824 ms 79532 KB Output is correct
22 Correct 484 ms 139528 KB Output is correct
23 Correct 608 ms 139444 KB Output is correct
24 Correct 414 ms 138416 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5040 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 10 ms 5288 KB Output is correct
9 Correct 9 ms 5332 KB Output is correct
10 Correct 8 ms 5276 KB Output is correct
11 Correct 9 ms 5368 KB Output is correct
12 Correct 8 ms 5204 KB Output is correct
13 Correct 7 ms 5416 KB Output is correct
14 Correct 8 ms 5436 KB Output is correct
15 Correct 7 ms 5428 KB Output is correct
16 Correct 5 ms 5460 KB Output is correct
17 Correct 6 ms 5304 KB Output is correct
18 Correct 5 ms 5180 KB Output is correct
19 Correct 1120 ms 140172 KB Output is correct
20 Correct 1126 ms 140320 KB Output is correct
21 Correct 1125 ms 140280 KB Output is correct
22 Correct 909 ms 139548 KB Output is correct
23 Correct 689 ms 139540 KB Output is correct
24 Correct 812 ms 138956 KB Output is correct
25 Correct 1603 ms 140364 KB Output is correct
26 Correct 890 ms 140272 KB Output is correct
27 Correct 1083 ms 140096 KB Output is correct
28 Correct 485 ms 139440 KB Output is correct
29 Correct 634 ms 139452 KB Output is correct
30 Correct 393 ms 138412 KB Output is correct
31 Correct 751 ms 79928 KB Output is correct
32 Correct 1061 ms 119916 KB Output is correct
33 Correct 1118 ms 140476 KB Output is correct
34 Correct 742 ms 77308 KB Output is correct
35 Correct 543 ms 77352 KB Output is correct
36 Correct 912 ms 118564 KB Output is correct
37 Correct 798 ms 79876 KB Output is correct
38 Correct 946 ms 97728 KB Output is correct
39 Correct 824 ms 79532 KB Output is correct
40 Correct 484 ms 139528 KB Output is correct
41 Correct 608 ms 139444 KB Output is correct
42 Correct 414 ms 138416 KB Output is correct
43 Correct 812 ms 81784 KB Output is correct
44 Correct 754 ms 81348 KB Output is correct
45 Correct 1095 ms 122204 KB Output is correct
46 Correct 708 ms 78236 KB Output is correct
47 Correct 494 ms 78632 KB Output is correct
48 Correct 319 ms 41832 KB Output is correct
49 Correct 1500 ms 121816 KB Output is correct
50 Correct 597 ms 81788 KB Output is correct
51 Correct 968 ms 121548 KB Output is correct
52 Correct 291 ms 78568 KB Output is correct
53 Correct 607 ms 140184 KB Output is correct