제출 #378169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378169		cheissmart	Examination (JOI19_examination)	C++14	100 / 100	1727 ms	52292 KiB

examination

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e5 + 7, C = 2e9 + 7;

array<int, 4> a[N * 2];
int ans[N];

struct node {
	node *l, *r;
	int val;
	node(int _val = 0) {
		l = r = nullptr;
		val = _val;
	}
};
node* root = nullptr;

void pull(node* t) {
	t -> val = (t -> l ? t -> l -> val : 0) + (t -> r ? t -> r -> val : 0);
}

void add(node*& t, int pos, int val, int tl = 0, int tr = C) {
	if(!t) t = new node();
	if(tr - tl == 1) {
		t -> val += val;
		return;
	}
	int tm = tl + (tr - tl) / 2;
	if(pos < tm) add(t -> l, pos, val, tl, tm);
	else add(t -> r, pos, val, tm, tr);
	pull(t);
}

int qry(node* t, int l, int r, int tl = 0, int tr = C) {
	if(!t) return 0;
	if(l <= tl && tr <= r) return t -> val;
	int tm = tl + (tr - tl) / 2;
	int ans = 0;
	if(l < tm) ans += qry(t -> l, l, r, tl, tm);
	if(r > tm) ans += qry(t -> r, l, r, tm, tr);
	return ans;	
}

void CDQ(int l, int r) {
	if(r - l == 1) return;
	int m = (l + r) / 2;
	CDQ(l, m), CDQ(m, r);
	sort(a + l, a + m, [&] (array<int, 4> x, array<int, 4> y) {
		return x[1] < y[1];
	});
	sort(a + m, a + r, [&] (array<int, 4> x, array<int, 4> y) {
		return x[1] < y[1];
	});
	vi undo;
	for(int i = m - 1, j = r - 1; i >= l; i--) {
		while(j >= m && a[j][1] >= a[i][1]) {
			if(a[j][3] == INF) {
				add(root, a[j][2], 1);
				undo.PB(a[j][2]);
			}
			j--;
		}
		if(a[i][3] != INF)
			ans[a[i][3]] += qry(root, a[i][2], C);		
	} 
	for(int i:undo) add(root, i, -1);
}

signed main()
{
	IO_OP;

	int n, q;
	cin >> n >> q;
	for(int i = 0; i < n; i++) {
		cin >> a[i][0] >> a[i][1];
		a[i][2] = a[i][0] + a[i][1];
		a[i][3] = INF;
	}
	for(int i = n; i < n + q; i++) {
		cin >> a[i][0] >> a[i][1] >> a[i][2];
		a[i][3] = i - n;
	}
	sort(a, a + n + q);
	CDQ(0, n + q);
	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';

}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57