32472023-02-23 11:57:20rennSzurikáta (45)cpp17Time limit exceeded 40/45319ms4760 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;
}

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);

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

            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;
}
SubtaskSumTestVerdictTimeMemory
base40/45
1Accepted0/03ms1956 KiB
2Accepted0/08ms2244 KiB
3Accepted2/23ms2260 KiB
4Accepted2/23ms2464 KiB
5Accepted2/24ms2704 KiB
6Accepted2/27ms2932 KiB
7Accepted2/27ms3140 KiB
8Accepted4/419ms3752 KiB
9Accepted4/417ms4004 KiB
10Accepted4/452ms3964 KiB
11Accepted4/493ms4096 KiB
12Accepted4/4150ms4340 KiB
13Accepted5/5207ms4436 KiB
14Accepted5/5263ms4644 KiB
15Time limit exceeded0/5319ms4760 KiB