245602026-02-12 17:54:16algoproSzurikáta (45)cpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base45/45
1Elfogadva0/01ms316 KiB
2Elfogadva0/025ms316 KiB
3Elfogadva2/22ms652 KiB
4Elfogadva2/22ms316 KiB
5Elfogadva2/26ms360 KiB
6Elfogadva2/224ms316 KiB
7Elfogadva2/223ms528 KiB
8Elfogadva4/461ms2052 KiB
9Elfogadva4/457ms1992 KiB
10Elfogadva4/450ms1964 KiB
11Elfogadva4/452ms2116 KiB
12Elfogadva4/454ms2100 KiB
13Elfogadva5/557ms2056 KiB
14Elfogadva5/557ms1944 KiB
15Elfogadva5/559ms1924 KiB