32072023-02-22 13:39:02rennSzurikáta (45)cpp17Runtime error 0/458ms5260 KiB
#include <bits/stdc++.h>
using namespace std;

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

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 right;
}

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 = INT_MIN, 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(INT_MAX);

    //cout << latjak << "\n";

    for (int i = 0, k, szi, mag, nszi, nmag, j; i < q; i++)
    {
        cin >> k;
        k--;
        cin >> szi >> mag;
        cnt = latjak;

        if(k == 0)
        {
            mer_temp = (double)(uregmag.at(szi)+mag-fa)/(double)uregek.at(szi);
            
            if(mer_temp > maxmer[szi])
            {
                cnt += !csucs[szi];
                j = bins_csucs(csucsok, szi, 0, csucsok.size());
                //cout << "szi: " << szi << " j: " << csucsok[j] << "\n";
                for (j; j < csucsok.size(); j++)
                {
                    if(maxmer[csucsok[j]] <= mer_temp)
                        cnt--;
                }
            }
            cout << cnt << " ";
            continue;
        }
        
        prev = maxmer[szi];
        cin >> nszi >> nmag;

        mer_temp = (double)(uregmag.at(szi)+mag-fa)/(double)uregek.at(szi);
        nmer_temp = (double)(uregmag.at(nszi)+nmag-fa)/(double)uregek.at(nszi);
        while(mer_temp <= prev)
        {
            if(--k < 0) break;

            szi = nszi, mag = nmag, mer_temp = nmer_temp;

            if(k > 0)
            {
                cin >> nszi >> nmag;
                nmer_temp = (double)(uregmag.at(nszi)+nmag-fa)/(double)uregek.at(nszi);
            }
        }

        if(k == -1)
        {
            if(mer_temp > maxmer[szi])
            {
                cnt += !csucs[szi];
                j = bins_csucs(csucsok, szi, 0, csucsok.size());
                //cout << "szi: " << szi << " j: " << csucsok[j] << "\n";
                for (j; j < csucsok.size(); j++)
                {
                    if(maxmer[csucsok[j]] <= mer_temp)
                        cnt--;
                }
            }
            cout << cnt << " ";
            continue;
        }
        else if(mer_temp > prev)
        {
            prev = mer_temp;
            cnt += !csucs[szi];
            //cout << "cnt1: " << cnt << "\n";

            j = bins_csucs(csucsok, szi, 0, csucsok.size());
            //cout << "szi: " << szi << " j: " << csucsok[j] << "\n";
            for (j; j < csucsok.size(); j++)
            {
                if(csucsok[j] == nszi)
                {
                    if(nmer_temp > prev)
                    {
                        prev = nmer_temp;
                    }
                    else
                    {
                        cnt--;
                        //cout << "cnt2: " << cnt << "\n";
                    }
                    if(--k > 0)
                    {
                        cin >> nszi >> nmag;
                        nmer_temp = (double)(uregmag.at(nszi)+nmag-fa)/(double)uregek.at(nszi);
                    }
                    else nmag = -1;
                    continue;
                }

                if(csucsok[j] > nszi && nmag >= 0)
                {
                    if(nmer_temp > prev)
                    {
                        prev = nmer_temp;
                        cnt += !csucs[nszi];
                        //cout << "cnt3: " << cnt << "\n";
                    }
                    else
                    {
                        cnt -= csucs[nszi];
                        //cout << "cnt4: " << cnt << "\n";
                    }
                    if(--k > 0)
                    {
                        cin >> nszi >> nmag;
                        nmer_temp = (double)(uregmag.at(nszi)+nmag-fa)/(double)uregek.at(nszi);
                        j--;
                    }
                    else if(csucsok[j] == INT_MAX) break;

                    continue;
                }

                if(csucsok[j] == INT_MAX) continue;

                if(maxmer[csucsok[j]] <= prev)
                    cnt--;
                //cout << "cnt5: " << cnt  << " " << maxmer[csucsok[j]] << " " << prev << "\n";
            }
            if(nmer_temp > prev)
                cnt += !csucs[nszi];
        }
        else
        {
            cnt -= (csucs[szi]);
            //cout << "cnt6: " << cnt << "\n";
        }
        cout << cnt << " ";
    }
    cout << "\n";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base0/45
1Runtime error0/03ms1888 KiB
2Runtime error0/03ms2152 KiB
3Runtime error0/23ms2348 KiB
4Runtime error0/23ms2444 KiB
5Runtime error0/23ms2544 KiB
6Runtime error0/23ms2768 KiB
7Runtime error0/23ms2776 KiB
8Runtime error0/48ms3980 KiB
9Runtime error0/48ms4140 KiB
10Runtime error0/47ms4316 KiB
11Runtime error0/48ms4856 KiB
12Runtime error0/48ms4948 KiB
13Runtime error0/57ms4856 KiB
14Runtime error0/57ms4884 KiB
15Runtime error0/57ms5260 KiB