Submission #969266

#	Time	Username	Problem	Language	Result	Execution time	Memory
969266		tset	The Potion of Great Power (CEOI20_potion)	C++14	21 / 100	1279 ms	262144 KiB

potion

    #include<bits/stdc++.h>
     
    using namespace std;
     
    #define pii pair<ll, ll>
    #define ll long long
    const ll INF =  1e18 + 42;
     
    ll nbElem, nbVoisinsMax, nbDays;
    vector<ll > alti;
    const ll SQRTDAY = 100;
    vector<set<ll > > save[SQRTDAY *2];
    vector<set<ll > > voisins;
    vector<ll > Us, Vs;
    void init(int N, int D, int F[])
    {
        nbElem = N;
        nbVoisinsMax = D;
        alti.resize(N);
        for(ll i=0; i<SQRTDAY *2; i++)
        {
            save[i].resize(N);
        }
        voisins.resize(N);
        for(ll i=0; i< N; i++)
        {
            alti[i] = F[i];
        }
    }
     
    void curseChanges(int U, int A[], int B[])
    {
        nbDays = U;
        for(ll iDay = 0; iDay < nbDays; iDay++)
        {
            if(iDay%SQRTDAY == 0)
            {
                save[iDay/SQRTDAY] = voisins;
            }
            ll u = A[iDay];
            ll v = B[iDay];
            if(voisins[u].find(v) != voisins[u].end())
            {
                voisins[u].erase(v);
                voisins[v].erase(u);
            }
            else
            {
                voisins[u].insert(v);
                voisins[v].insert(u);
            }
            Us.push_back(A[iDay]);
            Vs.push_back(B[iDay]);
        }
    }
     
    int question(int X, int Y, int V)
    {
        V--;
        ll day = V;
        set<ll> vx, vy;
        ll backupDate = day/SQRTDAY;
        vx = save[backupDate][X];
        vy = save[backupDate][Y];
        for(ll dayRecover = backupDate*SQRTDAY; dayRecover<= day; dayRecover++)
        {
            ll u = Us[dayRecover];
            ll v = Vs[dayRecover];
            //printf("[%lld/%lld]\n", u, v);
            if(u == X)
            {
                if(vx.find(v) != vx.end())
     
                    vx.erase(v);
                else
                    vx.insert(v);
            }
            if(v == X)
            {
                if(vx.find(u) != vx.end())
                    vx.erase(u);
                else
                    vx.insert(u);
            }
     
            if(u == Y)
            {
                if(vy.find(v) != vy.end())
                    vy.erase(v);
                else
                    vy.insert(v);
            }
            if(v == Y)
            {
                if(vy.find(u) != vy.end())
                    vy.erase(u);
                else
                    vy.insert(u);
            }
            
        }
        ll ans = INF;
        vector<pii > altis;
        for(ll valX : vx)
        {
            altis.push_back({alti[valX], 0});
        }
        for(ll valY: vy)
        {
            altis.push_back({alti[valY], 1});
        }
        sort(altis.begin(), altis.end());
        vector<ll> lasts(2, -INF);
        for(pii altiAct : altis)
        {
            lasts[altiAct.second] =  altiAct.first;
            ans=  min(ans, abs(lasts[0] - lasts[1]));
        }
        if(ans == INF)
            return 1000000000;
        return ans;
     
    }

• Subtask 1: 0 / 0
• Subtask 2: 0 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 30