32032023-02-22 13:10:42rennSzurikáta (45)cpp17Wrong answer 0/45163ms5416 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 mid;
}

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

    //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);
                    }
                    continue;
                }

                if(csucsok[j] > nszi)
                {
                    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--;
                    }
                    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 << " ";
    }
    
}
SubtaskSumTestVerdictTimeMemory
base0/45
1Accepted0/03ms1824 KiB
2Wrong answer0/07ms2220 KiB
3Wrong answer0/23ms2204 KiB
4Runtime error0/24ms2976 KiB
5Wrong answer0/24ms2880 KiB
6Wrong answer0/27ms2940 KiB
7Wrong answer0/27ms3188 KiB
8Wrong answer0/414ms4020 KiB
9Wrong answer0/414ms4236 KiB
10Wrong answer0/437ms4592 KiB
11Runtime error0/412ms5400 KiB
12Wrong answer0/486ms5144 KiB
13Wrong answer0/5114ms5144 KiB
14Wrong answer0/5138ms5180 KiB
15Wrong answer0/5163ms5416 KiB