31912023-02-22 10:08:34TuruTamasSzurikáta (45)cpp17Time limit exceeded 10/45400ms3884 KiB
#include <bits/stdc++.h>

using namespace std;

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

void maxUpTo(vector<double>& v) {
    double currentMax = v[0];
    for (double& i : v) {
        i = max(i, currentMax);
        initiallyVisible.push_back(i == currentMax);
        currentMax = i;
    }
}

int reCount(vector<double>& v) {
    double currentMax = v[0];
    int c = 1;
    for (double& i : v) {
        // cout << fixed << currentMax << ' ' << i << " " << (i > currentMax) << "\n"; 
        if (i > currentMax) c++;
        currentMax = max(i, currentMax);
    }
    return c;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> N >> P >> Q;
    int x;
    vector<double> slopes;
    int a;
    for (size_t i = 0; i < N; i++)
    {
        cin >> a;
        X.push_back({a, 0});
    }
    // cout << "Initial slopes ";
    for (size_t i = 0; i < N; i++)
    {
        cin >> a;
        X[i].second = a;
        slopes.push_back( (double)( X[i].second - P ) / (X[i].first) );
        // cout << fixed << (double)( X[i].second - P ) / (X[i].first) << " ";
    }
    // cout << "\n";
    for (size_t q = 0; q < Q; q++)
    {
        int Db; cin >> Db;
        int index, m;
        vector<pair<int, double>> changes;
        for (size_t i = 0; i < Db; i++)
        {
            cin >> index >> m;
            index--;
            double newslope = ( (double)( X[index].second + m - P ) / (X[index].first) );
            if (newslope < slopes[index]) continue;
            changes.push_back({index, slopes[index]});
            // cout << "wrote " << fixed << newslope << " to " << index << " replacing " << fixed << slopes[index] << "\n";
            slopes[index] = newslope;
        }
        cout << reCount(slopes) << ' ';
        for (pair<int, double> & val : changes)
        {
            slopes[val.first] = val.second;
        }
    }
}
SubtaskSumTestVerdictTimeMemory
base10/45
1Accepted0/03ms1828 KiB
2Accepted0/028ms2188 KiB
3Accepted2/23ms2332 KiB
4Accepted2/23ms2544 KiB
5Accepted2/217ms2908 KiB
6Accepted2/217ms3144 KiB
7Accepted2/217ms3348 KiB
8Time limit exceeded0/4400ms3332 KiB
9Time limit exceeded0/4370ms3532 KiB
10Time limit exceeded0/4367ms3548 KiB
11Time limit exceeded0/4354ms3604 KiB
12Time limit exceeded0/4375ms3768 KiB
13Time limit exceeded0/5384ms3556 KiB
14Time limit exceeded0/5360ms3828 KiB
15Time limit exceeded0/5384ms3884 KiB