oj.uz

Submission #477808

# Submission time Handle Problem Language Result Execution time Memory
477808 2021-10-04T00:59:45 Z hollwo_pelw Examination (JOI19_examination) C++17
100 / 100
 286 ms 10768 KB 
/*
// is short or still long ???
hollwo_pelw's template(short)
// Note : -Dhollwo_pelw_local
*/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

void FAST_IO(string filein = "", string fileout = "", string fileerr = ""){
	if (fopen(filein.c_str(), "r")){
		freopen(filein.c_str(), "r", stdin);
		freopen(fileout.c_str(), "w", stdout);
#ifdef hollwo_pelw_local
		freopen(fileerr.c_str(), "w", stderr);
#endif
	}
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
}

void Hollwo_Pelw();

signed main(){
#ifdef hollwo_pelw_local
	FAST_IO("input.inp", "output.out", "error.err");
	auto start = chrono::steady_clock::now();
#else
	FAST_IO("hollwo_pelw.inp", "hollwo_pelw.out");
#endif
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
	return 0;
}

const int N = 1e5 + 5, Q = 1e5 + 5;

struct item_t {
	int a, b, c, id;
} item[N + Q], tmp[N + Q];

int n, m, res[Q];

int list_x[N + Q], nx;
int list_y[N + Q], ny;

struct fenwick_tree {
	int bit[N + Q], ver[N + Q], vercnt;
 
	inline void add(int p, int x) {
		for (; p > 0; p -= p & -p) {
			if (ver[p] ^ vercnt)
				bit[p] = 0, ver[p] = vercnt;
			bit[p] += x;
		}
	}
	
	inline int query(int p) {
		int r = 0;
		for (; p < N + Q; p += p & -p) {
			if (ver[p] ^ vercnt)
				bit[p] = 0, ver[p] = vercnt;
			r += bit[p];
		}
		return r;
	}
 
	inline void clear() {
		++ vercnt;
	}
} bit;

void solve(int l, int r) {
	if (l == r) return ;
	int m = l + r >> 1;
	solve(l, m), solve(m + 1, r);

	// sort by x then query by y
	int i = l, j = m + 1, k = l;
	while (i <= m && j <= r) {
		if (item[i].a >= item[j].a) {
			if (!item[i].id)
				bit.add(item[i].b, 1);
			tmp[k ++] = item[i ++];
		} else {
			if (item[j].id)
				res[item[j].id] += bit.query(item[j].b);
			tmp[k ++] = item[j ++];
		}
	}

	while (i <= m) {
		tmp[k ++] = item[i ++];
	}

	while (j <= r) {
		if (item[j].id)
			res[item[j].id] += bit.query(item[j].b);
		tmp[k ++] = item[j ++];
	}

	bit.clear();
	for (int _ = l; _ <= r; _++)
		item[_] = tmp[_];

	// cout << "solve " << l << ' ' << r << '\n';
	// for (int i = l; i <= r; i++)
	// 	cout << "{" << item[i].a << ", " << item[i].b << ", " << item[i].id << "} ";
	// cout << '\n';
}

void Hollwo_Pelw() {
	cin >> n >> m;
	for (int i = 1, a, b; i <= n; i++)
		cin >> a >> b, item[i] = {a, b, a + b, 0};
	for (int i = 1, a, b, t; i <= m; i++)
		cin >> a >> b >> t, item[i + n] = {a, b, t, i};
	sort(item + 1, item + n + m + 1, [](const item_t& a, const item_t& b){
		return a.c > b.c || (a.c == b.c && a.id < b.id);
	});

	for (int i = 1; i <= n + m; i++) {
		list_x[i] = item[i].a;
		list_y[i] = item[i].b;
	}

	sort(list_x + 1, list_x + n + m + 1);
	nx = unique(list_x + 1, list_x + n + m + 1) - list_x;

	sort(list_y + 1, list_y + n + m + 1);
	ny = unique(list_y + 1, list_y + n + m + 1) - list_y;

	for (int i = 1; i <= n + m; i++) {
		item[i].a = lower_bound(list_x + 1, list_x + nx + 1, item[i].a) - list_x;
		item[i].b = lower_bound(list_y + 1, list_y + ny + 1, item[i].b) - list_y;
		// cout << "{" << item[i].a << ", " << item[i].b << ", " << item[i].id << "} ";
	}
	// cout << '\n';

	solve(1, n + m);
	for (int i = 1; i <= m; i++)
		cout << res[i] << '\n';
}

Compilation message

examination.cpp: In function 'void solve(int, int)':
examination.cpp:88:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |  int m = l + r >> 1;
      |          ~~^~~
examination.cpp: In function 'void FAST_IO(std::string, std::string, std::string)':
examination.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   freopen(filein.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen(fileout.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 6 ms 664 KB Output is correct
8 Correct 7 ms 716 KB Output is correct
9 Correct 6 ms 588 KB Output is correct
10 Correct 5 ms 652 KB Output is correct
11 Correct 6 ms 588 KB Output is correct
12 Correct 4 ms 588 KB Output is correct
13 Correct 6 ms 588 KB Output is correct
14 Correct 7 ms 616 KB Output is correct
15 Correct 7 ms 588 KB Output is correct
16 Correct 5 ms 588 KB Output is correct
17 Correct 4 ms 588 KB Output is correct
18 Correct 4 ms 588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 9792 KB Output is correct
2 Correct 233 ms 9740 KB Output is correct
3 Correct 238 ms 9872 KB Output is correct
4 Correct 163 ms 9072 KB Output is correct
5 Correct 170 ms 9796 KB Output is correct
6 Correct 116 ms 9120 KB Output is correct
7 Correct 225 ms 9796 KB Output is correct
8 Correct 236 ms 9620 KB Output is correct
9 Correct 228 ms 9568 KB Output is correct
10 Correct 157 ms 9540 KB Output is correct
11 Correct 155 ms 8896 KB Output is correct
12 Correct 107 ms 8760 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 9792 KB Output is correct
2 Correct 233 ms 9740 KB Output is correct
3 Correct 238 ms 9872 KB Output is correct
4 Correct 163 ms 9072 KB Output is correct
5 Correct 170 ms 9796 KB Output is correct
6 Correct 116 ms 9120 KB Output is correct
7 Correct 225 ms 9796 KB Output is correct
8 Correct 236 ms 9620 KB Output is correct
9 Correct 228 ms 9568 KB Output is correct
10 Correct 157 ms 9540 KB Output is correct
11 Correct 155 ms 8896 KB Output is correct
12 Correct 107 ms 8760 KB Output is correct
13 Correct 270 ms 9748 KB Output is correct
14 Correct 252 ms 9728 KB Output is correct
15 Correct 243 ms 9740 KB Output is correct
16 Correct 181 ms 9028 KB Output is correct
17 Correct 199 ms 9708 KB Output is correct
18 Correct 123 ms 9088 KB Output is correct
19 Correct 254 ms 9748 KB Output is correct
20 Correct 258 ms 9796 KB Output is correct
21 Correct 253 ms 9924 KB Output is correct
22 Correct 167 ms 9612 KB Output is correct
23 Correct 139 ms 8900 KB Output is correct
24 Correct 102 ms 8732 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 6 ms 664 KB Output is correct
8 Correct 7 ms 716 KB Output is correct
9 Correct 6 ms 588 KB Output is correct
10 Correct 5 ms 652 KB Output is correct
11 Correct 6 ms 588 KB Output is correct
12 Correct 4 ms 588 KB Output is correct
13 Correct 6 ms 588 KB Output is correct
14 Correct 7 ms 616 KB Output is correct
15 Correct 7 ms 588 KB Output is correct
16 Correct 5 ms 588 KB Output is correct
17 Correct 4 ms 588 KB Output is correct
18 Correct 4 ms 588 KB Output is correct
19 Correct 241 ms 9792 KB Output is correct
20 Correct 233 ms 9740 KB Output is correct
21 Correct 238 ms 9872 KB Output is correct
22 Correct 163 ms 9072 KB Output is correct
23 Correct 170 ms 9796 KB Output is correct
24 Correct 116 ms 9120 KB Output is correct
25 Correct 225 ms 9796 KB Output is correct
26 Correct 236 ms 9620 KB Output is correct
27 Correct 228 ms 9568 KB Output is correct
28 Correct 157 ms 9540 KB Output is correct
29 Correct 155 ms 8896 KB Output is correct
30 Correct 107 ms 8760 KB Output is correct
31 Correct 270 ms 9748 KB Output is correct
32 Correct 252 ms 9728 KB Output is correct
33 Correct 243 ms 9740 KB Output is correct
34 Correct 181 ms 9028 KB Output is correct
35 Correct 199 ms 9708 KB Output is correct
36 Correct 123 ms 9088 KB Output is correct
37 Correct 254 ms 9748 KB Output is correct
38 Correct 258 ms 9796 KB Output is correct
39 Correct 253 ms 9924 KB Output is correct
40 Correct 167 ms 9612 KB Output is correct
41 Correct 139 ms 8900 KB Output is correct
42 Correct 102 ms 8732 KB Output is correct
43 Correct 286 ms 10524 KB Output is correct
44 Correct 278 ms 10560 KB Output is correct
45 Correct 285 ms 10768 KB Output is correct
46 Correct 179 ms 9104 KB Output is correct
47 Correct 211 ms 10564 KB Output is correct
48 Correct 133 ms 9028 KB Output is correct
49 Correct 285 ms 10648 KB Output is correct
50 Correct 286 ms 10564 KB Output is correct
51 Correct 265 ms 10616 KB Output is correct
52 Correct 191 ms 10564 KB Output is correct
53 Correct 156 ms 8948 KB Output is correct