31762023-02-21 13:52:44TuruTamasSzurikáta (45)cpp17Time limit exceeded 14/45374ms4580 KiB
#include <bits/stdc++.h>

using namespace std;

int N, P, Q;
vector<pair<int, int>> X;
vector<double> maxslopes;

void  getGood(vector<double>& v) {
    double cmax = v[0];
    maxslopes.push_back(cmax);
    for (size_t i = 1; i < v.size(); i++)
    {
        cmax = max(v[i], cmax);
        maxslopes.push_back(cmax);
    }
}

int doCrap(vector<double>& slope) {
    double maxslope = slope[0];
    int count = 1;
    for (size_t i = 1; i < slope.size(); i++)
    {
        if (slope[i] > maxslope) {
            count++;
            maxslope = slope[i];
        }
    }
    return count;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> N >> P >> Q;
    int x;
    vector<double> slope;
    cout.precision(17);
    X.assign(N, {0, 0});
    for (size_t i = 0; i < N; i++)
    {
        cin >> x;
        X[i].first = x;
    }
    
    for (size_t i = 0; i < N; i++)
    {
        cin >> x;
        X[i].second = x;
        slope.push_back((double)((double)(x-P)/(double)X[i].first));
    }
    getGood(slope);
    vector<double> slope2 = slope;
    for (size_t q = 0; q < Q; q++)
    {
        int Db; cin >> Db;
        vector<pair<int, int>> kkckm;   
        int a, b;
        for (size_t i = 0; i < Db; i++)
        {
            cin >> a >> b;
            a--;
            double newslope = (double)((double)(X[a].second+b-P)/(double)X[a].first);
            if (newslope < maxslopes[a]) {
                continue;
            }
            kkckm.push_back({a, b});
            slope2[a] = newslope;
        }
        cout << doCrap(slope2) << ' ';
        for (pair<int, int>& x : kkckm)
        {
            slope2[x.first] = slope[x.first];
        }
        
    }
}
SubtaskSumTestVerdictTimeMemory
base14/45
1Accepted0/03ms1824 KiB
2Accepted0/012ms2192 KiB
3Accepted2/23ms2244 KiB
4Accepted2/23ms2452 KiB
5Accepted2/27ms2828 KiB
6Accepted2/28ms2784 KiB
7Accepted2/29ms3040 KiB
8Time limit exceeded0/4374ms3232 KiB
9Accepted4/4270ms4580 KiB
10Time limit exceeded0/4358ms3476 KiB
11Time limit exceeded0/4360ms3752 KiB
12Time limit exceeded0/4356ms3944 KiB
13Time limit exceeded0/5360ms4192 KiB
14Time limit exceeded0/5372ms4132 KiB
15Time limit exceeded0/5361ms3976 KiB