oj.uz

답안 #124616

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -