oj.uz

Submission #630304

# Submission time Handle Problem Language Result Execution time Memory
630304 2022-08-16T07:32:11 Z pooyashams Examination (JOI19_examination) C++14
100 / 100
 1630 ms 137916 KB 
// 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.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 4948 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 5204 KB Output is correct
8 Correct 9 ms 5204 KB Output is correct
9 Correct 9 ms 5204 KB Output is correct
10 Correct 8 ms 5204 KB Output is correct
11 Correct 8 ms 5204 KB Output is correct
12 Correct 9 ms 5204 KB Output is correct
13 Correct 7 ms 5332 KB Output is correct
14 Correct 7 ms 5372 KB Output is correct
15 Correct 9 ms 5368 KB Output is correct
16 Correct 5 ms 5332 KB Output is correct
17 Correct 6 ms 5204 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1128 ms 137916 KB Output is correct
2 Correct 1120 ms 137904 KB Output is correct
3 Correct 1158 ms 137784 KB Output is correct
4 Correct 917 ms 137836 KB Output is correct
5 Correct 712 ms 137788 KB Output is correct
6 Correct 826 ms 137844 KB Output is correct
7 Correct 1630 ms 137788 KB Output is correct
8 Correct 888 ms 137788 KB Output is correct
9 Correct 1086 ms 137832 KB Output is correct
10 Correct 482 ms 137700 KB Output is correct
11 Correct 613 ms 137660 KB Output is correct
12 Correct 432 ms 137448 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1128 ms 137916 KB Output is correct
2 Correct 1120 ms 137904 KB Output is correct
3 Correct 1158 ms 137784 KB Output is correct
4 Correct 917 ms 137836 KB Output is correct
5 Correct 712 ms 137788 KB Output is correct
6 Correct 826 ms 137844 KB Output is correct
7 Correct 1630 ms 137788 KB Output is correct
8 Correct 888 ms 137788 KB Output is correct
9 Correct 1086 ms 137832 KB Output is correct
10 Correct 482 ms 137700 KB Output is correct
11 Correct 613 ms 137660 KB Output is correct
12 Correct 432 ms 137448 KB Output is correct
13 Correct 767 ms 77088 KB Output is correct
14 Correct 1087 ms 117084 KB Output is correct
15 Correct 1108 ms 137756 KB Output is correct
16 Correct 676 ms 75200 KB Output is correct
17 Correct 519 ms 75260 KB Output is correct
18 Correct 778 ms 117512 KB Output is correct
19 Correct 747 ms 76908 KB Output is correct
20 Correct 936 ms 94888 KB Output is correct
21 Correct 805 ms 76712 KB Output is correct
22 Correct 477 ms 137660 KB Output is correct
23 Correct 620 ms 137676 KB Output is correct
24 Correct 391 ms 137452 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 4948 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 5204 KB Output is correct
8 Correct 9 ms 5204 KB Output is correct
9 Correct 9 ms 5204 KB Output is correct
10 Correct 8 ms 5204 KB Output is correct
11 Correct 8 ms 5204 KB Output is correct
12 Correct 9 ms 5204 KB Output is correct
13 Correct 7 ms 5332 KB Output is correct
14 Correct 7 ms 5372 KB Output is correct
15 Correct 9 ms 5368 KB Output is correct
16 Correct 5 ms 5332 KB Output is correct
17 Correct 6 ms 5204 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Correct 1128 ms 137916 KB Output is correct
20 Correct 1120 ms 137904 KB Output is correct
21 Correct 1158 ms 137784 KB Output is correct
22 Correct 917 ms 137836 KB Output is correct
23 Correct 712 ms 137788 KB Output is correct
24 Correct 826 ms 137844 KB Output is correct
25 Correct 1630 ms 137788 KB Output is correct
26 Correct 888 ms 137788 KB Output is correct
27 Correct 1086 ms 137832 KB Output is correct
28 Correct 482 ms 137700 KB Output is correct
29 Correct 613 ms 137660 KB Output is correct
30 Correct 432 ms 137448 KB Output is correct
31 Correct 767 ms 77088 KB Output is correct
32 Correct 1087 ms 117084 KB Output is correct
33 Correct 1108 ms 137756 KB Output is correct
34 Correct 676 ms 75200 KB Output is correct
35 Correct 519 ms 75260 KB Output is correct
36 Correct 778 ms 117512 KB Output is correct
37 Correct 747 ms 76908 KB Output is correct
38 Correct 936 ms 94888 KB Output is correct
39 Correct 805 ms 76712 KB Output is correct
40 Correct 477 ms 137660 KB Output is correct
41 Correct 620 ms 137676 KB Output is correct
42 Correct 391 ms 137452 KB Output is correct
43 Correct 765 ms 76956 KB Output is correct
44 Correct 802 ms 76380 KB Output is correct
45 Correct 1093 ms 117336 KB Output is correct
46 Correct 666 ms 74992 KB Output is correct
47 Correct 491 ms 75308 KB Output is correct
48 Correct 329 ms 40812 KB Output is correct
49 Correct 1518 ms 117108 KB Output is correct
50 Correct 589 ms 76924 KB Output is correct
51 Correct 970 ms 116908 KB Output is correct
52 Correct 301 ms 75380 KB Output is correct
53 Correct 604 ms 137636 KB Output is correct