245602026-02-12 17:54:16algoproSzurikáta (45)cpp17Accepted 45/4561ms2116 KiB
// UUID: e249aaa4-ab15-43ce-8e04-6ca3550d7759
#include <bits/stdc++.h>

using namespace std;


int n, q;
long long p;
double x[100005], y[100005], s[100005];

struct Node {
    double mx; 
    int cnt;   
} tree[400005];

int calc(int v, int tl, int tr, double limit) {
    if (tree[v].mx <= limit) return 0;
    if (tl == tr) return tree[v].mx > limit ? 1 : 0;
    
    int tm = (tl + tr) / 2;
    if (tree[2 * v].mx <= limit) {
        return calc(2 * v + 1, tm + 1, tr, limit);
    }
    return calc(2 * v, tl, tm, limit) + (tree[v].cnt - tree[2 * v].cnt);
}

void update(int v, int tl, int tr, int pos, double val) {
    if (tl == tr) {
        tree[v].mx = val;
        tree[v].cnt = 1;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) update(2 * v, tl, tm, pos, val);
        else update(2 * v + 1, tm + 1, tr, pos, val);
        
        tree[v].mx = max(tree[2 * v].mx, tree[2 * v + 1].mx);
        tree[v].cnt = tree[2 * v].cnt + calc(2 * v + 1, tm + 1, tr, tree[2 * v].mx);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> p >> q;

    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) {
        cin >> y[i];
        s[i] = (y[i] - p) / x[i];
        update(1, 1, n, i, s[i]);
    }

    while (q--) {
        int db;
        cin >> db;
        vector<pair<int, double>> original;
        for (int i = 0; i < db; i++) {
            int idx;
            long long dy;
            cin >> idx >> dy;
            original.push_back({idx, s[idx]});
            double new_s = (y[idx] + dy - p) / x[idx];
            update(1, 1, n, idx, new_s);
        }

        cout << tree[1].cnt << (q == 0 ? "" : " ");

        for (auto &p : original) {
            update(1, 1, n, p.first, p.second);
        }
    }
    cout << endl;

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base45/45
1Accepted0/01ms316 KiB
2Accepted0/025ms316 KiB
3Accepted2/22ms652 KiB
4Accepted2/22ms316 KiB
5Accepted2/26ms360 KiB
6Accepted2/224ms316 KiB
7Accepted2/223ms528 KiB
8Accepted4/461ms2052 KiB
9Accepted4/457ms1992 KiB
10Accepted4/450ms1964 KiB
11Accepted4/452ms2116 KiB
12Accepted4/454ms2100 KiB
13Accepted5/557ms2056 KiB
14Accepted5/557ms1944 KiB
15Accepted5/559ms1924 KiB