245592026-02-12 17:53:48algoproSzurikáta (45)cpp17Accepted 45/4561ms2104 KiB
// UUID: d3f67cba-6cda-421d-8b0a-65c8fc51d7d5
#include <iostream>
#include <vector>
#include <algorithm>

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);

    if (!(cin >> n >> p >> q)) return 0;

    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/024ms316 KiB
3Accepted2/22ms316 KiB
4Accepted2/22ms316 KiB
5Accepted2/26ms316 KiB
6Accepted2/224ms528 KiB
7Accepted2/223ms316 KiB
8Accepted4/461ms2092 KiB
9Accepted4/459ms2096 KiB
10Accepted4/452ms2100 KiB
11Accepted4/452ms2088 KiB
12Accepted4/454ms1996 KiB
13Accepted5/557ms2100 KiB
14Accepted5/557ms2104 KiB
15Accepted5/559ms2100 KiB