Submission #1207086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207086		TIN	Examination (JOI19_examination)	C++20	100 / 100	457 ms	52040 KiB

examination

#include <bits/stdc++.h>

using namespace std;

#define FNAME "test"

const int N = 1e5 + 5;

int n, q;

struct Data {
	int x, y, z;

	Data() : x(0), y(0), z(0) {}

	Data(int x, int y) : x(x), y(y), z(x + y) {}

	Data(int x, int y, int z) : x(x), y(y), z(z) {}

	void rev() {
		x = -x, y = -y, z = -z;
	}
};

Data student[N], query[N];

struct COORD {
	vector<int> data;

	COORD() {
		data.clear();
	}

	COORD(vector<int> data) : data(data) {}

	void add(int v) {
		data.push_back(v);
	}

	void compress() {
		sort(data.begin(), data.end());
		data.resize(unique(data.begin(), data.end()) - data.begin());
	}

	int size() {
		return (int) data.size();
	}

	int geq(int v) {
		return lower_bound(data.begin(), data.end(), v) - data.begin() + 1;
	}

	int leq(int v) {
		return upper_bound(data.begin(), data.end(), v) - data.begin();
	}
};

COORD X, Y, Z;

struct Event {
	int t;
	int x, y;
	int id;

	Event() {}

	Event(int t, int x, int y, int id) : t(t), x(x), y(y), id(id) {}
};

vector<Event> events[N * 2];

struct FenwickTree2D {
	int mxX, mxY;
	vector<COORD> nodes;
	vector<vector<int>> f;

	void init(int _mxX, int _mxY) {
		mxX = _mxX, mxY = _mxY;
		nodes.resize(_mxX + 1);
		f.resize(_mxX + 1);
	}

	void initNodes() {
		for (int x = 1; x <= mxX; x++) {
			nodes[x].compress();
			f[x].resize(nodes[x].size() + 1);
		}
	}

	void fakeUpdate(int x, int y) {
		for (; x <= mxX; x += x & (-x)) nodes[x].add(y);
	}

	void fakeGet(int x, int y) {
		for (; x > 0; x -= x & (-x)) nodes[x].add(y);
	}

	void update(int u, int v) {
		for (int x = u; x <= mxX; x += x & (-x))
			for (int y = nodes[x].geq(v); y <= nodes[x].size(); y += y & (-y))
				f[x][y]++;
	}

	int get(int u, int v) {
		int ret = 0;
		for (int x = u; x > 0; x -= x & (-x))
			for (int y = nodes[x].leq(v); y > 0; y -= y & (-y))
				ret += f[x][y];
		return ret;
	}
} BIT2D;

int ans[N];

void Task() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(9);
	if (fopen(FNAME".inp","r")) {
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

void Input() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int a, b; cin >> a >> b;
		student[i] = Data(a, b);
	}
	for (int i = 1; i <= q; i++) {
		int alpha, beta, gamma;
		cin >> alpha >> beta >> gamma;
		query[i] = Data(alpha, beta, gamma);
	}
}

void compress() {
	for (int i = 1; i <= n; i++) student[i].rev();
	for (int i = 1; i <= n; i++) {
		X.add(student[i].x);
		Y.add(student[i].y);
		Z.add(student[i].z);
	}
	for (int i = 1; i <= q; i++) query[i].rev();
	for (int i = 1; i <= q; i++) {
		X.add(query[i].x);
		Y.add(query[i].y);
		Z.add(query[i].z);
	}
	X.compress();
	Y.compress();
	Z.compress();
	for (int i = 1; i <= n; i++) {
		student[i].x = X.geq(student[i].x);
		student[i].y = Y.geq(student[i].y);
		student[i].z = Z.geq(student[i].z);
	}
	for (int i = 1; i <= q; i++) {
		query[i].x = X.geq(query[i].x);
		query[i].y = Y.geq(query[i].y);
		query[i].z = Z.geq(query[i].z);
	}
}

void buildEvent() {
	for (int i = 1; i <= n; i++) events[student[i].z].push_back(Event(0, student[i].x, student[i].y, i));
	for (int i = 1; i <= q; i++) events[query[i].z].push_back(Event(1, query[i].x, query[i].y, i));
}

void solve() {
	BIT2D.init(X.size(), Y.size());
	for (int z = 1; z <= Z.size(); z++) {
		for (auto event : events[z]) {
			if (event.t == 0) BIT2D.fakeUpdate(event.x, event.y);
			if (event.t == 1) BIT2D.fakeGet(event.x, event.y);
		}
	}
	BIT2D.initNodes();
	for (int z = 1; z <= Z.size(); z++) {
		for (auto event : events[z]) {
			if (event.t == 0) BIT2D.update(event.x, event.y);
			if (event.t == 1) ans[event.id] = BIT2D.get(event.x, event.y);
		}
	}
	for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

void Solve() {
	//Your Code
	Input();
	compress();
	buildEvent();
	solve();
}

int main() {
	Task();
	Solve();
	cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
	return 37^37;
}

Compilation message (stderr)

examination.cpp: In function 'void Task()':
examination.cpp:120:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:121:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57