32162023-02-22 17:18:10sztomiSzurikáta (45)cpp11Accepted 45/4523ms4732 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);


    int n, p, q;
    cin >> n >> p >> q;
    vector<int> helyek(n);
    for(int& x : helyek){
        cin >> x;
    }
    vector<int> magassagok(n);
    for(int& x : magassagok){
        cin >> x;
    }

    vector<double> meredekseg(n);
    for(int i = 0; i < n; i++){
        meredekseg[i] = (double)(magassagok[i] - p) / helyek[i];
    }
    vector<int> lat;
    lat.push_back(0);
    for(int i = 1; i < n; i++){
        if(meredekseg[i] > meredekseg[lat.back()]){
            lat.push_back(i);
        }
    }

    int db;
    int hol, mennyit;
    while(q--){
        cin >> db;
        vector<double> ujak(db);
        // valodi index, ujakon beluli index
        // melyik szurikatak, akik tutira kilatszanak egymas mogul
        vector<pii> uj_lat;
        for(int i = 0; i < db; i++){
            cin >> hol >> mennyit;
            hol--;
            ujak[i] = (double)(magassagok[hol] + mennyit - p) / helyek[hol];
            if(uj_lat.size() == 0 || ujak[i] > ujak[uj_lat.back().second]){
                uj_lat.push_back({hol, i});
            }
        }

        //cout << "---------------------------------------\n";
        // kivalogatjuk azokat az emelkedokat,amik kilatszanak az alap cucc mogul
        vector<pii> latszok;
        for(int i = 0; i < uj_lat.size(); i++){
            // megkeressuk azt a helyet, ami utan kerulne
            int kerul = -1;
            int l = 0, r = lat.size()-1;
            while(l <= r){
                int mid = (l + r) / 2;
                if(lat[mid] < uj_lat[i].first){
                    kerul = mid;
                    l = mid + 1;
                }
                else{
                    r = mid - 1;
                }
            }
            //cout << "ujlat " << uj_lat[i].first << " " << uj_lat[i].second << "\n";
            //cout << "kerul: " << kerul << "\n";
            //cout << "meredek1: " << meredekseg[lat[kerul]] << "\n";
            //cout << "meredek2: " << ujak[uj_lat[i].second] << "\n";

            // megnezzuk egyaltalan latszik-e
            if(kerul != -1){
                if(meredekseg[lat[kerul]] < ujak[uj_lat[i].second]){
                    //cout << "nem latszik\n";
                    latszok.push_back(uj_lat[i]);
                }
            }
            else{
                latszok.push_back(uj_lat[i]);
            }
        }

        int ki = lat.size();
        for(int i = 0; i < latszok.size(); i++){
            //cout << "latszik " << latszok[i].first << " " << latszok[i].second << "\n";
            // megkeressuk, hogy ki utan kerulne
            int kerul = -1;
            int l = 0, r = lat.size()-1;
            while(l <= r){
                int mid = (l + r) / 2;
                if(lat[mid] < latszok[i].first){
                    kerul = mid;
                    l = mid + 1;
                }
                else{
                    r = mid - 1;
                }
            }

            int kovi_hely;
            if(i == latszok.size()-1){
                kovi_hely = n;
            }
            else{
                kovi_hely = latszok[i+1].first;
            }

            // megkeressuk, hogy melyik az utolso, amelyiket eltakarna
            int vege = -1;
            l = kerul+1;
            r = lat.size()-1;
            while(l <= r){
                int mid = (l+r) / 2;
                // ne szamoljunk duplan semmit, ezert csak a kovetkezo emelkedoig nezzuk
                if(lat[mid] >= kovi_hely){
                    r = mid-1;
                    continue;
                }
                if(meredekseg[lat[mid]] <= ujak[latszok[i].second]){
                    vege = mid;
                    l = mid + 1;
                }
                else{
                    r = mid - 1;
                }
            }

            //cout << "kerul: " << kerul << " vege: " << vege << "\n";

            ki++;
            if(vege != -1){
                ki -= vege - (kerul+1) + 1;
            }
        }

        //cout << "ki: " << ki << "\n";
        //cout << "------------------------------------\n";
        cout << ki << " ";
    }
    cout << "\n";
}
SubtaskSumTestVerdictTimeMemory
base45/45
1Accepted0/03ms1828 KiB
2Accepted0/08ms2184 KiB
3Accepted2/23ms2244 KiB
4Accepted2/23ms2452 KiB
5Accepted2/24ms2812 KiB
6Accepted2/28ms3144 KiB
7Accepted2/28ms3360 KiB
8Accepted4/417ms3976 KiB
9Accepted4/414ms4064 KiB
10Accepted4/414ms4404 KiB
11Accepted4/414ms4316 KiB
12Accepted4/417ms4380 KiB
13Accepted5/519ms4384 KiB
14Accepted5/521ms4528 KiB
15Accepted5/523ms4732 KiB