242172026-02-06 16:49:33zsomborSzurikáta (45)cpp17Elfogadva 45/4520ms5892 KiB
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int n, p, q, k, mx = 0, sz = 0, ans;
vector <ll> x(2e5, 0);
vector <ll> y(2e5, 0);
vector <int> v(2e5, 0);
vector <int> inv(2e5, 0);
vector <int> a;
vector <int> b;

bool R(int i, int j) {
	return y[i] * x[j] < y[j] * x[i];
}

void bs(int x, int y) {
	int l = inv[x], r = (inv[y] == y ? inv[y] : inv[y] + 1), m;
	while (r - l > 1) {
		m = (r + l) / 2;
		(R(x, v[m]) ? r = m : l = m);
	}
	ans -= l - inv[x];
}

void solve() {
	cin >> k;
	a.resize(k);
	b.resize(k);
	for (int i = 0; i < k; i++) {
		cin >> a[i] >> b[i];
		y[a[i]] += b[i];
	}
	a.push_back(n + 1);
	ans = sz;
	for (int i = 0, j; i < k; i = j) {
		int x = a[i];
		if (R(v[inv[x]], x)) ans++;
		j = i + 1;
		while (!R(x, a[j])) j++;
		bs(x, a[j]);
	}
	for (int i = 0; i < k; i++) y[a[i]] -= b[i];
	cout << ans << " ";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> p >> q;
	x[0] = 1; y[0] = -1e9;
	for (int i = 1; i <= n; i++) cin >> x[i];
	for (int i = 1; i <= n; i++) {
		cin >> y[i];
		y[i] -= p;
		if (R(mx, i)) { v[++sz] = i; mx = i; };
		inv[i] = sz;
	}
	x[n + 1] = 1; y[n + 1] = 1e9;
	v[sz + 1] = n + 1;
	inv[n + 1] = sz + 1;
	while (q--) solve();
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base45/45
1Elfogadva0/04ms4916 KiB
2Elfogadva0/09ms5172 KiB
3Elfogadva2/24ms4916 KiB
4Elfogadva2/26ms5108 KiB
5Elfogadva2/27ms5172 KiB
6Elfogadva2/29ms5260 KiB
7Elfogadva2/29ms5260 KiB
8Elfogadva4/417ms5640 KiB
9Elfogadva4/417ms5892 KiB
10Elfogadva4/416ms5428 KiB
11Elfogadva4/417ms5620 KiB
12Elfogadva4/417ms5428 KiB
13Elfogadva5/517ms5428 KiB
14Elfogadva5/519ms5684 KiB
15Elfogadva5/520ms5672 KiB