32522023-02-23 12:14:19rennSzurikáta (45)cpp17Futási hiba 0/4534ms4512 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;
            if((double)(uregmag[szi]+mag-fa)/(double)(uregek[szi]) > maxmer[szi-1])
            {
                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
base0/45
1Elfogadva0/03ms1832 KiB
2Futási hiba0/03ms2300 KiB
3Futási hiba0/23ms2388 KiB
4Futási hiba0/23ms2620 KiB
5Futási hiba0/23ms2836 KiB
6Futási hiba0/23ms2828 KiB
7Futási hiba0/23ms3028 KiB
8Futási hiba0/48ms3812 KiB
9Futási hiba0/48ms4116 KiB
10Futási hiba0/48ms4280 KiB
11Futási hiba0/413ms4260 KiB
12Futási hiba0/414ms4488 KiB
13Futási hiba0/534ms4300 KiB
14Futási hiba0/514ms4296 KiB
15Futási hiba0/58ms4512 KiB