제출 #795322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
795322		acatmeowmeow	Examination (JOI19_examination)	C++11	100 / 100	986 ms	55084 KiB

examination

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;
int n, q, A[N + 5], B[N + 5], X[N + 5], Y[N + 5], Z[N + 5], arrIndex[N + 5], queryIndex[N + 5], ans[N + 5];
vector<int> node[2*N + 5], tree[2*N + 5];

void fakeUpdate(int x, int y) {
	for (; x <= 2*N; x += x&-x) node[x].push_back(y);
}

void fakeQuery(int x, int y){
	for (; x; x -= x&-x) node[x].push_back(y);
}

void compress() {
	for (int i = 1; i <= 2*N; i++) {
		sort(node[i].begin(), node[i].end());
		node[i].erase(unique(node[i].begin(), node[i].end()), node[i].end());
		tree[i].resize(node[i].size() + 1);
	}
}

void update(int x, int y, int v) {
	for (; x <= 2*N; x += x&-x) {
		for (int yy = lower_bound(node[x].begin(), node[x].end(), y) - node[x].begin() + 1; yy <= node[x].size(); yy += yy&-yy) {
			tree[x][yy] += v;
		}
	}
}

int query(int x, int y) {
	int res = 0;
	for (; x; x -= x&-x) {
		for (int yy = lower_bound(node[x].begin(), node[x].end(), y) - node[x].begin() + 1; yy; yy -= yy&-yy) {
			res += tree[x][yy];
		}
	}
	return res;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> A[i] >> B[i];
	for (int i = 1; i <= q; i++) cin >> X[i] >> Y[i] >> Z[i];
	vector<int> mp1, mp2;
	for (int i = 1; i <= n; i++) mp1.push_back(A[i]), mp2.push_back(B[i]);
	for (int i = 1; i <= q; i++) mp1.push_back(X[i]), mp2.push_back(Y[i]);
	sort(mp1.begin(), mp1.end());
	sort(mp2.begin(), mp2.end());
	auto getIndex = [&](int a, vector<int>&p) { return lower_bound(p.begin(), p.end(), a) - p.begin() + 1; };
	
	iota(arrIndex + 1, arrIndex + n + 1, 1ll);
	sort(arrIndex + 1, arrIndex + n + 1, [&](int a, int b) {
			tuple<int, int, int> f = {A[a] + B[a], A[a], B[a]}, se = {A[b] + B[b], A[b], B[b]};
			return f > se;
	});

	iota(queryIndex + 1, queryIndex + q + 1, 1ll);
	sort(queryIndex + 1, queryIndex + q + 1, [&](int a, int b) {
			tuple<int, int, int> f = {Z[a], X[a], Y[a]}, se = {Z[b], X[b], Y[b]};
			return f > se;
	});

	for (int i = 1; i <= q; i++) {
		int mpX = getIndex(X[i], mp1), mpY = getIndex(Y[i], mp2);
		fakeQuery(2*N, 2*N);
		fakeQuery(2*N, mpY - 1);
		fakeQuery(mpX - 1, 2*N);
		fakeQuery(mpX - 1, mpY - 1);
	}

	for (int i = 1; i <= n; i++) {
		int mpA = getIndex(A[i], mp1), mpB = getIndex(B[i], mp2);
		fakeUpdate(mpA, mpB);
	}
	compress();
	
	for (int i = 1, index = 1; i <= q; i++) {
		int pos = queryIndex[i];
		while (index <= n && A[arrIndex[index]] + B[arrIndex[index]] >= Z[pos]) {
			int mpA = getIndex(A[arrIndex[index]], mp1), mpB = getIndex(B[arrIndex[index]], mp2);
			update(mpA, mpB, 1);
			index++;
		}
		int mpX = getIndex(X[pos], mp1), mpY = getIndex(Y[pos], mp2);
		ans[pos] = query(2*N, 2*N) - query(2*N, mpY - 1) - query(mpX - 1, 2*N) + query(mpX - 1, mpY - 1);
	}
	
	for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'void update(int, int, int)':
examination.cpp:27:90: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int yy = lower_bound(node[x].begin(), node[x].end(), y) - node[x].begin() + 1; yy <= node[x].size(); yy += yy&-yy) {
      |                                                                                       ~~~^~~~~~~~~~~~~~~~~

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