oj.uz

Submission #124614

# Submission time Handle Problem Language Result Execution time Memory
124614 2019-07-03T15:06:30 Z Just_Solve_The_Problem Examination (JOI19_examination) C++14
0 / 100
 308 ms 35668 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <iostream>
#include <memory.h>

using namespace std;

const int N = (int)1e5 + 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 = upper_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

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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 700 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 756 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 20 ms 2004 KB Output is correct
8 Correct 19 ms 1872 KB Output is correct
9 Correct 18 ms 1984 KB Output is correct
10 Correct 16 ms 1896 KB Output is correct
11 Correct 16 ms 1852 KB Output is correct
12 Incorrect 13 ms 1856 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 308 ms 35668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 308 ms 35668 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 700 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 756 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 20 ms 2004 KB Output is correct
8 Correct 19 ms 1872 KB Output is correct
9 Correct 18 ms 1984 KB Output is correct
10 Correct 16 ms 1896 KB Output is correct
11 Correct 16 ms 1852 KB Output is correct
12 Incorrect 13 ms 1856 KB Output isn't correct
13 Halted 0 ms 0 KB -