32352023-02-23 10:19:49rennSzurikáta (45)cpp17Futási hiba 0/45375ms5220 KiB
#include <bits/stdc++.h>
using namespace std;

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

inline int s_csucs(vector<int> &csucsok, int tg, int left, int right)
{
    for (int i = 0; i < right; i++)
    {
        if(csucsok[i] == tg)
            return i+1;
        
        if(csucsok[i] > tg)
            return i;
    }
    return right-1;
}

inline int bins_csucs(vector<int> &csucsok, int tg, int left, int right)
{
    int mid;
    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+1;
}

int main()
{
    GOTTAGOFAST

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

    vector<double> maxmer(n+1);

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

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

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

    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();
        pszi = szi;

        //cout << "debug4\n";

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

        bool br = false;

        //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";

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

                    if(csucsok[i] > szik.front()) // ha elhagytam a kövi pontot
                    {
                        //cout << "elhagyta\n";
                        br = false;
                        pszi = szi;
                        szi = szik.front();
                        mag = magk.front();
                        mer_temp = (double)(uregmag[szi]+mag-fa)/(double)(uregek[szi]);
                        szik.pop();
                        magk.pop();
                        break;
                    }
                }

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

    cout << "\n";
    return 1;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/45
1Futási hiba0/03ms1976 KiB
2Futási hiba0/08ms2276 KiB
3Futási hiba0/23ms2260 KiB
4Futási hiba0/23ms2376 KiB
5Futási hiba0/24ms2608 KiB
6Futási hiba0/27ms2912 KiB
7Futási hiba0/27ms3116 KiB
8Futási hiba0/423ms3868 KiB
9Futási hiba0/418ms4144 KiB
10Futási hiba0/468ms4492 KiB
11Futási hiba0/4126ms4972 KiB
12Futási hiba0/4197ms5124 KiB
13Futási hiba0/5270ms5220 KiB
14Időlimit túllépés0/5344ms5104 KiB
15Időlimit túllépés0/5375ms3796 KiB