oj.uz

Submission #383967

# Submission time Handle Problem Language Result Execution time Memory
383967 2021-03-31T05:52:37 Z nikatamliani Examination (JOI19_examination) C++14
0 / 100
 506 ms 15952 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+10;
template <typename T>
struct implicit_segment_tree {
	T neutral;
	int size, max_size;
	function<T(T, T)> join;
	vector<T> values;
	vector<int> left, right;
	implicit_segment_tree(int _max_size, T _neutral, function<T(T, T)> f, int reserve_size = 1) {
		join = f;
		neutral = _neutral;
		size = 0;
		max_size = _max_size;
		values.reserve(reserve_size);
		left.reserve(reserve_size);
		right.reserve(reserve_size);
		insert_node(neutral);
	}
	
	T get_val(int pos) {
		if(pos < 0 || pos >= (int)values.size()) return neutral;
		return values[pos];
	}
	
	void insert_node(T val) {
		values.push_back(val);
		left.push_back(-1);
		right.push_back(-1);
		++size;
	}
	
	void point_update(int id, T val) {
		point_update(1, max_size, id, val, 0); 
	}
	
	void point_update(int l, int r, int x, T val, int p) {
		int middle = l + r >> 1;
		if(l == r) {
			values[p] = val;
			return;
		}
		if(x <= middle) {
			if(left[p] == -1) {
				left[p] = size;
				insert_node(neutral);
			}
			point_update(l, middle, x, val, left[p]);
		} else {
			if(right[p] == -1) {
				right[p] = size;
				insert_node(neutral);
			}
			point_update(middle+1, r, x, val, right[p]);
		}
		values[p] = join(get_val(left[p]), get_val(right[p]));
	}
	
	T get(int id) {
		return query(id, id);
	}
	
	T query(int L, int R) {
		if(L > R) return neutral;
		return query(1, max_size, L, R, 0); 
	}
	
	T query(int l, int r, int L, int R, int p) {
		if(L > r || l > R || p == -1) return neutral;
		if(L <= l && R >= r) return get_val(p);
		int middle = l + r >> 1;
		T lft = query(l, middle, L, R, left[p]);
		T rgh = query(middle+1, r, L, R, right[p]);
		return join(lft, rgh);
	}
	
	void print_tree(int n) {
		for(int i = 1; i <= n; ++i) {
			cout << get(i) << " \n"[i == n];
		}
	}
};
struct point {
	int x, y, sum, id;
	bool operator < (const point &other) {
		return sum < other.sum;
	}
};
main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m; 
	vector<point> a(n), b(m);
	for(int i = 0; i < n; ++i) {
		cin >> a[i].x >> a[i].y;
		a[i].sum = a[i].x + a[i].y;
	}
	for(int i = 0; i < m; ++i) {
		cin >> b[i].x >> b[i].y >> b[i].sum;
		b[i].sum = max(b[i].sum, b[i].x + b[i].y);
		b[i].id = i;
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	vector<int> ans(m);
	auto sum = [](int x, int y) -> int {
		return x + y;
	};
	implicit_segment_tree<int> tx(INT_MAX, 0, sum);
	implicit_segment_tree<int> ty(INT_MAX, 0, sum); 
	for(int i = m - 1, j = n - 1; i >= 0; --i) {
		while(j >= 0 && a[j].sum >= b[i].sum) {
			int upd_x = tx.get(a[j].x) + 1;
			int upd_y = ty.get(a[j].y) + 1;
			tx.point_update(a[j].x, upd_x);
			ty.point_update(a[j].y, upd_y);
			--j;
		}
		ans[b[i].id] = n - j - 1 - tx.query(1, b[i].x - 1) - ty.query(1, b[i].y - 1);
	}
	for(int x : ans) {
		cout << x << ' ';  
	}
}

Compilation message

examination.cpp:91:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main() {
      |      ^
examination.cpp: In instantiation of 'void implicit_segment_tree<T>::point_update(long long int, long long int, long long int, T, long long int) [with T = long long int]':
examination.cpp:36:3:   required from 'void implicit_segment_tree<T>::point_update(long long int, T) [with T = long long int]'
examination.cpp:117:33:   required from here
examination.cpp:40:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int middle = l + r >> 1;
      |                ~~^~~
examination.cpp: In instantiation of 'T implicit_segment_tree<T>::query(long long int, long long int, long long int, long long int, long long int) [with T = long long int]':
examination.cpp:67:36:   required from 'T implicit_segment_tree<T>::query(long long int, long long int) [with T = long long int]'
examination.cpp:121:52:   required from here
examination.cpp:73:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |   int middle = l + r >> 1;
      |                ~~^~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 14 ms 3864 KB Output is correct
8 Correct 14 ms 3840 KB Output is correct
9 Correct 14 ms 3536 KB Output is correct
10 Incorrect 11 ms 2264 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 506 ms 15952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 506 ms 15952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 14 ms 3864 KB Output is correct
8 Correct 14 ms 3840 KB Output is correct
9 Correct 14 ms 3536 KB Output is correct
10 Incorrect 11 ms 2264 KB Output isn't correct
11 Halted 0 ms 0 KB -