Submission #383970

#	Time	Username	Problem	Language	Result	Execution time	Memory
383970		nikatamliani	Examination (JOI19_examination)	C++14	100 / 100	781 ms	76116 KiB

examination

#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(-max_size, 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(-max_size, 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(0, b[i].x - 1) - ty.query(0, b[i].y - 1);
	}
	for(int x : ans) {
		cout << x << ' ';  
	}
}

Compilation message (stderr)

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:44:   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: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57