oj.uz

Submission #124616

# Submission time Handle Problem Language Result Execution time Memory
124616 2019-07-03T15:07:30 Z Just_Solve_The_Problem Examination (JOI19_examination) C++14
2 / 100
 309 ms 33248 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 = 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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 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 18 ms 1728 KB Output is correct
8 Correct 18 ms 1724 KB Output is correct
9 Correct 18 ms 1852 KB Output is correct
10 Correct 16 ms 1856 KB Output is correct
11 Correct 16 ms 1728 KB Output is correct
12 Correct 13 ms 1728 KB Output is correct
13 Correct 16 ms 1856 KB Output is correct
14 Correct 16 ms 1980 KB Output is correct
15 Correct 16 ms 1984 KB Output is correct
16 Correct 13 ms 2024 KB Output is correct
17 Correct 16 ms 1864 KB Output is correct
18 Correct 11 ms 1856 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 309 ms 33248 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 309 ms 33248 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 764 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 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 18 ms 1728 KB Output is correct
8 Correct 18 ms 1724 KB Output is correct
9 Correct 18 ms 1852 KB Output is correct
10 Correct 16 ms 1856 KB Output is correct
11 Correct 16 ms 1728 KB Output is correct
12 Correct 13 ms 1728 KB Output is correct
13 Correct 16 ms 1856 KB Output is correct
14 Correct 16 ms 1980 KB Output is correct
15 Correct 16 ms 1984 KB Output is correct
16 Correct 13 ms 2024 KB Output is correct
17 Correct 16 ms 1864 KB Output is correct
18 Correct 11 ms 1856 KB Output is correct
19 Runtime error 309 ms 33248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -