oj.uz

Submission #375084

# Submission time Handle Problem Language Result Execution time Memory
375084 2021-03-09T02:26:07 Z 8e7 Examination (JOI19_examination) C++14
100 / 100
 256 ms 18164 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
//#include <bits/extc++.h>
#define ll long long
#define maxn 300005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
//using namespace __gnu_pbds;
//template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//find by order, order of key

struct obj {
	int x, y, z, type, id;
	obj() {
		x = 0, y = 0, z = 0, type = 0, id = 0;
	}
	obj(int a, int b, int c, int d) {
		x = a, y = b, z = c, type = d, id = 0;
	}
};
vector<obj> v, v2;
bool cut[maxn];

inline bool cmp(obj a, obj b) {
	if (a.z == b.z) return a.type < b.type;
	return a.z > b.z;
}
inline bool cmp2(obj a, obj b) {
	if (a.x == b.x) {
		if (a.y == b.y) return a.type < b.type;
		return a.y < b.y;
	}
	return a.x < b.x;
}

vector<int> nx, ny;
inline void compress(vector<int> &a) {
	sort(a.begin(), a.end());

	a.resize(int(unique(a.begin(), a.end()) - a.begin()));
}

struct BIT{
	int bit[maxn];
	void modify(int ind, int val) {
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += val;
	}
	int query(int ind) {
		int ret = 0;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret;
	}
} bx, by, bb;

int ans[maxn];
int main() {
	io
	int n, q;
	cin >> n >> q;
	for (int i = 0;i < n;i++) {
		int s, t;
		cin >> s >> t;
		v.push_back(obj(s, t, s + t, 0));
		nx.push_back(s);
		ny.push_back(t);
	}
	for (int i = 0;i < q;i++) {
		int x, y, z;
		cin >> x >> y >> z;
		v.push_back(obj(x, y, z, 1));
		cut[i] = z > x + y;
		v.back().id = i;
		nx.push_back(x);
		ny.push_back(y);
	}
	sort(v.begin(), v.end(), cmp);

	//for (int i:nx) cout << i << " ";
	//cout << endl;
	compress(nx), compress(ny);
	//for (int i:nx) cout << i << " ";
	//cout << endl;
	for (auto &i:v) {
		i.x = lower_bound(nx.begin(), nx.end(), i.x) - nx.begin() + 1;
		i.y = lower_bound(ny.begin(), ny.end(), i.y) - ny.begin() + 1;
		//cout << i.x << " " << i.y << " " << i.z << " " << i.type << endl;
	}


	int les = n;
	for (int i = 0;i < v.size();i++) {
		if (v[i].type == 0) {
			bx.modify(v[i].x, 1);
			by.modify(v[i].y, 1);
			v2.push_back(obj(maxn - 1 - v[i].x, maxn - 1 - v[i].y, 0, 0));
			les--;
		} else {
			if (cut[v[i].id]) {
				ans[v[i].id] = n - les - bx.query(v[i].x - 1) - by.query(v[i].y - 1);
			} else {
				//ans[v[i].id] = n - bx.query(v[i].x - 1) - by.query(v[i].y - 1);
				v2.push_back(obj(maxn - v[i].x - 1, maxn - v[i].y - 1, 0, 1));
				v2.back().id = v[i].id;
			}
		}
	}
	sort(v2.begin(), v2.end(), cmp2);
	for (int i = 0;i < v2.size();i++) {
		if (v2[i].type == 0) {
			bb.modify(v2[i].y, 1);
		} else {
			ans[v2[i].id] = bb.query(v2[i].y);
		}
	}

	for (int i = 0;i < q;i++) cout << ans[i] << "\n";
}
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100

10 10
41304 98327
91921 28251
85635 59191
30361 72671
28949 96958
99041 37826
10245 2726
19387 20282
60366 87723
95388 49726
52302 69501 66009
43754 45346 3158
25224 58881 18727
7298 24412 63782
24107 10583 61508
65025 29140 7278
36104 56758 2775
23126 67608 122051
56910 17272 62933
39675 15874 117117

 */

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<obj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for (int i = 0;i < v.size();i++) {
      |                 ~~^~~~~~~~~~
examination.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<obj>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  for (int i = 0;i < v2.size();i++) {
      |                 ~~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 7 ms 992 KB Output is correct
8 Correct 8 ms 992 KB Output is correct
9 Correct 7 ms 992 KB Output is correct
10 Correct 6 ms 876 KB Output is correct
11 Correct 7 ms 876 KB Output is correct
12 Correct 5 ms 876 KB Output is correct
13 Correct 6 ms 992 KB Output is correct
14 Correct 6 ms 992 KB Output is correct
15 Correct 8 ms 992 KB Output is correct
16 Correct 5 ms 992 KB Output is correct
17 Correct 5 ms 876 KB Output is correct
18 Correct 5 ms 896 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 17068 KB Output is correct
2 Correct 227 ms 17220 KB Output is correct
3 Correct 229 ms 17140 KB Output is correct
4 Correct 177 ms 16524 KB Output is correct
5 Correct 217 ms 16848 KB Output is correct
6 Correct 136 ms 16244 KB Output is correct
7 Correct 219 ms 17140 KB Output is correct
8 Correct 238 ms 17012 KB Output is correct
9 Correct 221 ms 17012 KB Output is correct
10 Correct 183 ms 16628 KB Output is correct
11 Correct 175 ms 17396 KB Output is correct
12 Correct 118 ms 16372 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 17068 KB Output is correct
2 Correct 227 ms 17220 KB Output is correct
3 Correct 229 ms 17140 KB Output is correct
4 Correct 177 ms 16524 KB Output is correct
5 Correct 217 ms 16848 KB Output is correct
6 Correct 136 ms 16244 KB Output is correct
7 Correct 219 ms 17140 KB Output is correct
8 Correct 238 ms 17012 KB Output is correct
9 Correct 221 ms 17012 KB Output is correct
10 Correct 183 ms 16628 KB Output is correct
11 Correct 175 ms 17396 KB Output is correct
12 Correct 118 ms 16372 KB Output is correct
13 Correct 231 ms 17140 KB Output is correct
14 Correct 238 ms 17340 KB Output is correct
15 Correct 228 ms 17652 KB Output is correct
16 Correct 183 ms 16116 KB Output is correct
17 Correct 188 ms 16372 KB Output is correct
18 Correct 139 ms 16392 KB Output is correct
19 Correct 232 ms 16628 KB Output is correct
20 Correct 232 ms 16884 KB Output is correct
21 Correct 221 ms 13044 KB Output is correct
22 Correct 171 ms 16628 KB Output is correct
23 Correct 168 ms 16372 KB Output is correct
24 Correct 120 ms 15732 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 7 ms 992 KB Output is correct
8 Correct 8 ms 992 KB Output is correct
9 Correct 7 ms 992 KB Output is correct
10 Correct 6 ms 876 KB Output is correct
11 Correct 7 ms 876 KB Output is correct
12 Correct 5 ms 876 KB Output is correct
13 Correct 6 ms 992 KB Output is correct
14 Correct 6 ms 992 KB Output is correct
15 Correct 8 ms 992 KB Output is correct
16 Correct 5 ms 992 KB Output is correct
17 Correct 5 ms 876 KB Output is correct
18 Correct 5 ms 896 KB Output is correct
19 Correct 231 ms 17068 KB Output is correct
20 Correct 227 ms 17220 KB Output is correct
21 Correct 229 ms 17140 KB Output is correct
22 Correct 177 ms 16524 KB Output is correct
23 Correct 217 ms 16848 KB Output is correct
24 Correct 136 ms 16244 KB Output is correct
25 Correct 219 ms 17140 KB Output is correct
26 Correct 238 ms 17012 KB Output is correct
27 Correct 221 ms 17012 KB Output is correct
28 Correct 183 ms 16628 KB Output is correct
29 Correct 175 ms 17396 KB Output is correct
30 Correct 118 ms 16372 KB Output is correct
31 Correct 231 ms 17140 KB Output is correct
32 Correct 238 ms 17340 KB Output is correct
33 Correct 228 ms 17652 KB Output is correct
34 Correct 183 ms 16116 KB Output is correct
35 Correct 188 ms 16372 KB Output is correct
36 Correct 139 ms 16392 KB Output is correct
37 Correct 232 ms 16628 KB Output is correct
38 Correct 232 ms 16884 KB Output is correct
39 Correct 221 ms 13044 KB Output is correct
40 Correct 171 ms 16628 KB Output is correct
41 Correct 168 ms 16372 KB Output is correct
42 Correct 120 ms 15732 KB Output is correct
43 Correct 253 ms 17396 KB Output is correct
44 Correct 256 ms 17396 KB Output is correct
45 Correct 254 ms 18164 KB Output is correct
46 Correct 189 ms 15848 KB Output is correct
47 Correct 196 ms 16756 KB Output is correct
48 Correct 129 ms 11764 KB Output is correct
49 Correct 249 ms 17524 KB Output is correct
50 Correct 254 ms 14532 KB Output is correct
51 Correct 235 ms 14196 KB Output is correct
52 Correct 189 ms 16500 KB Output is correct
53 Correct 253 ms 16756 KB Output is correct