Submission #477808

#	Time	Username	Problem	Language	Result	Execution time	Memory
477808		hollwo_pelw	Examination (JOI19_examination)	C++17	100 / 100	286 ms	10768 KiB

examination

/*
// 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 (stderr)

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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57