31962023-02-22 11:47:05TuruTamasSzurikáta (45)cpp17Wrong answer 8/45379ms4744 KiB
#include <bits/stdc++.h>
#include <float.h>

using namespace std;

int N, P, Q;
vector<pair<int, int>> X;
vector<double> maxslopes;
int initCount = 1;
vector<bool> initVisible;

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

int reCount(vector<double>& slopes, vector<pair<int, double>>& changes) {
    int r = initCount;
    // cout << (int)(changes.size())-1 << endl;
    for (int i = 0; i < (int)(changes.size())-1; i++)
    {
        
        if (!initVisible[changes[i].first]) r++;
        // cout << "asdf" << endl;
        for (size_t k = changes[i].first+1; k < changes[i+1].first; k++)
        {
            if (slopes[k] > changes[i].second) break;
            r -= initVisible[k];
        }
    }
    pair<int, double> last = changes[changes.size()-1];
    if (!initVisible[last.first]) r++;
    for (size_t k = last.first+1; k < slopes.size(); k++)
    {
        if (slopes[k] > last.second) break;
        r -= initVisible[k];
    }
    return r;
}

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";
    maxUpTo(slopes);
    for (size_t q = 0; q < Q; q++)
    {
        int Db; cin >> Db;
        int index, m;
        vector<pair<int, double>> changes;
        double currentMax = -DBL_MAX;
        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] || newslope < currentMax) continue;
            currentMax = max(currentMax, newslope);
            changes.push_back({index, newslope});
            // cout << "wrote " << fixed << newslope << " to " << index << " replacing " << fixed << slopes[index] << "\n";
        }
        if (changes.empty()) cout << initCount << " ";
        else cout << reCount(slopes, changes) << " ";
    }
}
SubtaskSumTestVerdictTimeMemory
base8/45
1Accepted0/03ms1824 KiB
2Wrong answer0/08ms2180 KiB
3Wrong answer0/23ms2344 KiB
4Wrong answer0/23ms2324 KiB
5Wrong answer0/24ms2352 KiB
6Wrong answer0/27ms2600 KiB
7Wrong answer0/28ms2928 KiB
8Wrong answer0/435ms4156 KiB
9Wrong answer0/428ms4320 KiB
10Accepted4/4122ms4536 KiB
11Wrong answer0/4186ms4532 KiB
12Accepted4/4247ms4592 KiB
13Time limit exceeded0/5314ms4744 KiB
14Time limit exceeded0/5370ms3516 KiB
15Time limit exceeded0/5379ms3616 KiB