Submission #383732

#	Time	Username	Problem	Language	Result	Execution time	Memory
383732		aryan12	Examination (JOI19_examination)	C++17	43 / 100	315 ms	57708 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct marks {
	int x, y, sum, idx;
};

struct tree {
	int l, r, val;
};


const int N = 1e5 + 5;
marks a[N], b[N];
int sz[2] = {1, 1};
tree seg[2][N * 4];

bool cmp(marks A, marks B) {
	return A.sum > B.sum;
}

void Update(int flag, int qpos, int pos, int l, int r) {
	//cout << l << " " << r << "\n";
	if(l == r) {
		//cout << "flag = " << flag << ", " << "qpos = " << qpos << ", pos = " << pos << ", l = " << l << ", r = " << r << "\n";
		seg[flag][pos].val++;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= qpos) {
		if(seg[flag][pos].l == 0) {
			seg[flag][pos].l = ++sz[flag];
		}
		Update(flag, qpos, seg[flag][pos].l, l, mid);
	}
	else {
		if(seg[flag][pos].r == 0) {
			seg[flag][pos].r = ++sz[flag];
		}
		Update(flag, qpos, seg[flag][pos].r, mid + 1, r);
	}
	seg[flag][pos].val = seg[flag][seg[flag][pos].l].val + seg[flag][seg[flag][pos].r].val;
}

int Query(int flag, int ql, int qr, int pos, int l, int r) {
	if(ql > r || l > qr || pos == 0 || l > r)
		return 0;
	if(ql <= l && r <= qr) {
		return seg[flag][pos].val;
	}
	int mid = (l + r) >> 1;
	return Query(flag, ql, qr, seg[flag][pos].l, l, mid) + Query(flag, ql, qr, seg[flag][pos].r, mid + 1, r);
}

void Solve() {
	int n, q;
	cin >> n >> q;
	marks temp;
	for(int i = 1; i <= n; i++) {
		cin >> temp.x >> temp.y;
		temp.sum = temp.x + temp.y;
		temp.idx = 0;
		a[i] = temp;
	}
	for(int i = 1; i <= q; i++) {
		cin >> temp.x >> temp.y >> temp.sum;
		temp.sum = max(temp.sum, temp.x + temp.y);
		temp.idx = i;
		b[i] = temp;
	}
	sort(a + 1, a + 1 + n, cmp);
	sort(b + 1, b + 1 + q, cmp);
	int ans[q + 1];
	int aPos = 1;
	for(int i = 1; i <= q; i++) {
		while(aPos != n + 1 && a[aPos].sum >= b[i].sum) {
			Update(0, a[aPos].x, 1, 0, INT_MAX);
			Update(1, a[aPos].y, 1, 0, INT_MAX);
			aPos++;
		}
		ans[b[i].idx] = aPos - 1 - Query(0, 0, b[i].x - 1, 1, 0, INT_MAX) - Query(1, 0, b[i].y - 1, 1, 0, INT_MAX);
	}
	for(int i = 1; i <= q; i++) {
		cout << ans[i] << "\n";
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Solve();
	return 0;
}

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