Submission #124617

#	Time	Username	Problem	Language	Result	Execution time	Memory
124617		Just_Solve_The_Problem	Examination (JOI19_examination)	C++14	100 / 100	771 ms	39672 KiB

examination

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <iostream>
#include <memory.h>

using namespace std;

const int N = (int)1e6 + 7;

int n, m;
pair <int, int> ar[N];

struct fen {
	int tree[N];
	fen() {
		memset(tree, 0, sizeof tree);
	}
	void upd(int pos, int val) {
		while (pos < N) {
			tree[pos] += val;
			pos = pos | pos + 1;
		}
	}
	int get(int r) {
		int res = 0;
		while (r >= 0) {
			res += tree[r];
			r = (r & r + 1) - 1;
		}
		return res;
	}
};
fen tr;

struct query {
	int id, tp, pos, x, y, val, z;
	query() {}
	query(int _pos, int _tp, int _x, int _y, int _z, int _val, int _id) {
		pos = _pos;
		tp = _tp;
		x = _x;
		id = _id;
		val = _val;
		z = _z;
		y = _y;
	}
};
vector <query> vec;
int ans[N];
query tp[N];

void make(int l, int r) {
	if (l >= r) return ;
	int mid = (l + r) >> 1;
	for (int i = l; i <= r; i++) {
		if (vec[i].pos <= mid && vec[i].tp == 0) {
			tr.upd(vec[i].y, vec[i].val);
		} else if (vec[i].pos > mid && vec[i].tp == 1) {
			ans[vec[i].id] += vec[i].val * tr.get(vec[i].y);
		}
	}
	for (int i = l; i <= r; i++) {
		if (vec[i].pos <= mid && vec[i].tp == 0) {
			tr.upd(vec[i].y, -vec[i].val);
		}
	}
	int curl = l;
	int curr = mid + 1;
	for (int i = l; i <= r; i++) {
		if (vec[i].pos <= mid) {
			tp[curl++] = vec[i];
		} else {
			tp[curr++] = vec[i];
		}
	}
	for (int i = l; i <= r; i++) {
		vec[i] = tp[i];
	}
	make(l, mid);
	make(mid + 1, r);
}

main() {
	scanf("%d %d", &n, &m);
	vector <int> vecx, vecy, vecz;
	for (int i = 1, x, y; i <= n; i++) {
		scanf("%d %d", &x, &y);
		vecx.push_back(x);
		vecy.push_back(y);
		vecz.push_back(x + y);
		ar[i] = {x, y};
	}
	sort(vecx.begin(), vecx.end());
	vecx.resize(unique(vecx.begin(), vecx.end()) - vecx.begin());
	sort(vecy.begin(), vecy.end());
	vecy.resize(unique(vecy.begin(), vecy.end()) - vecy.begin());
	sort(vecz.begin(), vecz.end());
	vecz.resize(unique(vecz.begin(), vecz.end()) - vecz.begin());
	int cnt = 0;
	for (int i = 1, x, y, z; i <= n; i++) {
		x = lower_bound(vecx.begin(), vecx.end(), ar[i].first) - vecx.begin();
		y = lower_bound(vecy.begin(), vecy.end(), ar[i].second) - vecy.begin();
		z = lower_bound(vecz.begin(), vecz.end(), ar[i].first + ar[i].second) - vecz.begin();
		vec.push_back(query(cnt++, 0, x, y, z, 1, 0));
	}
	
	for (int i = 1, x, y, z; i <= m; i++) {
		scanf("%d %d %d", &x, &y, &z);
		x = lower_bound(vecx.begin(), vecx.end(), x) - vecx.begin();
		y = lower_bound(vecy.begin(), vecy.end(), y) - vecy.begin();
		z = lower_bound(vecz.begin(), vecz.end(), z) - vecz.begin();
		// cout << x << ' ' << y << ' ' << z << endl;
		vec.push_back(query(cnt++, 1, vec.size(), vec.size(), z, 1, i));
		vec.push_back(query(cnt++, 1, x - 1, vec.size(), z, -1, i));
		vec.push_back(query(cnt++, 1, vec.size(), y - 1, z, -1, i));
		vec.push_back(query(cnt++, 1, x - 1, y - 1, z, 1, i));
	}
	sort(vec.begin(), vec.end(), [&](const auto &A, const auto &B) {
		if (A.z == B.z) return A.id < B.id; 
		return A.z > B.z;
	});
	/*
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i].tp << ' ' << vec[i].x << ' ' << vec[i].y << ' ' << vec[i].z << endl;
	}
	*/
	cnt = 0;
	for (int i = 0; i < vec.size(); i++) {
		vec[i].pos = cnt++;
	}
	sort(vec.begin(), vec.end(), [&](const auto &A, const auto &B) {
		if (A.x == B.x) return A.pos < B.pos;
		return A.x < B.x;
	});
	make(0, vec.size() - 1);
	for (int i = 1; i <= m; i++) {
		printf("%d\n", ans[i]);
	}
}

Compilation message (stderr)

examination.cpp: In member function 'void fen::upd(int, int)':
examination.cpp:24:20: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
    pos = pos | pos + 1;
                ~~~~^~~
examination.cpp: In member function 'int fen::get(int)':
examination.cpp:31:15: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
    r = (r & r + 1) - 1;
             ~~^~~
examination.cpp: At global scope:
examination.cpp:86:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
examination.cpp: In function 'int main()':
examination.cpp:131:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++) {
                  ~~^~~~~~~~~~~~
examination.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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