32532023-02-23 12:15:40rennSzurikáta (45)cpp17Elfogadva 45/45277ms4736 KiB
#include <bits/stdc++.h>
using namespace std;

#define GOTTAGOFAST cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);

int mid;

inline int bins_csucs(vector<int> &csucsok, int tg, int left, int right)
{
    while(left <= right)
    {
        mid = left+(right-left)/2;
        if(csucsok[mid] == tg)
            return mid+1;

        if(csucsok[mid] < tg)
        {
            left = mid+1;
        }
        else
        {
            right = mid-1;
        }
    }

    return left;
}

int main()
{
    GOTTAGOFAST

    int n, fa, q;
    cin >> n >> fa >> q;
    vector<int> uregek(n+1);
    vector<int> uregmag(n+1);
    vector<bool> csucs(n+1, false);
    vector<int> csucsok;

    vector<double> maxmer(n+1);
    maxmer[0] = -100000000;

    for (int i = 1; i <= n; i++)
    {
        cin >> uregek[i];
    }

    int latjak = 0, cnt;
    double prev = -100000000, mer_temp;

    for (int i = 1, j; i <= n; i++)
    {
        cin >> j;
        uregmag.at(i) = j; 
        mer_temp = (double)(j-fa)/(double)uregek.at(i);
        if(mer_temp > prev)
        {
            csucs.at(i) = true;
            csucsok.push_back(i);
            
            prev = mer_temp;
            latjak++;
        }
        maxmer.at(i) = prev;
    }
    csucsok.push_back(100000000);
    int i, ii, k;
    int szi, mag;

    queue<int> szik;
    queue<int> magk;

    //cout << "debug1\n";

    while(q--)
    {
        //cout << "debug2\n";
        cin >> k;
        while(k--)
        {
            //cout << "debug3\n";
            cin >> szi >> mag;
            szik.push(szi);
            magk.push(mag);
        }

        cnt = latjak;

        szi = szik.front();
        mag = magk.front();

        mer_temp = (double)(uregmag[szi]+mag-fa)/(double)(uregek[szi]);

        szik.pop();
        magk.pop();

        //cout << "debug4\n";

        prev = maxmer[szi];
        i = bins_csucs(csucsok, szi, 0, csucsok.size());

        bool br;

        //cout << "debug5\n";

        while(true)
        {
            br = true;
            //cout << "debug6\n";
            if(mer_temp > prev) // ha magasabb, mint az előző
            {
                //cout << "debug7\n";
                cnt += !csucs[szi]; // 1 ha korábban nem látta, 0 ha korábban is látta
                prev = mer_temp;
            }
            else // ha nem magasabb, mint az előző
            {
                //cout << "debug8\n";
                cnt -= csucs[szi]; // 1 ha korábban csúcs volt, 0 ha korábban se látta
            }

            //cout << "debug9\n";

            ii = i;

            /*while(true)
            {
                mid = ii+(csucsok.size()-ii)/2;

                if()
            }*/

            for(i; i < csucsok.size(); i++)
            {
                //cout << "csucs: " << csucsok[i] << "\n";
                if(!szik.empty())
                {
                    if(csucsok[i] >= szik.front()) // ha elértem a kövi pontot
                    {
                        //cout << "elerte\n";
                        br = false;
                        szi = szik.front();
                        mag = magk.front();
                        mer_temp = (double)(uregmag[szi]+mag-fa)/(double)(uregek[szi]);
                        szik.pop();
                        magk.pop();
                        i += (csucsok[i] == szi);
                        break;
                    }
                }

                //cout << "debug10\n";
                if(csucsok[i] > n) continue;
                if(maxmer[csucsok[i]] <= prev)
                    cnt--;
                else
                    prev = maxmer[csucsok[i]];
                //cout << "debug11\n";
            }
            if(br) break;
        }
        cout << cnt << " ";
    }

    cout << "\n";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base45/45
1Elfogadva0/03ms1828 KiB
2Elfogadva0/08ms2208 KiB
3Elfogadva2/23ms2388 KiB
4Elfogadva2/23ms2460 KiB
5Elfogadva2/24ms2820 KiB
6Elfogadva2/27ms2776 KiB
7Elfogadva2/27ms2772 KiB
8Elfogadva4/418ms3564 KiB
9Elfogadva4/416ms3648 KiB
10Elfogadva4/446ms3644 KiB
11Elfogadva4/482ms3904 KiB
12Elfogadva4/4131ms3972 KiB
13Elfogadva5/5180ms4220 KiB
14Elfogadva5/5230ms4472 KiB
15Elfogadva5/5277ms4736 KiB