oj.uz

Submission #969266

# Submission time Handle Problem Language Result Execution time Memory
969266 2024-04-24T20:43:42 Z tset The Potion of Great Power (CEOI20_potion) C++14
21 / 100
 1279 ms 262144 KB 
    #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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10328 KB Output is correct
2 Correct 7 ms 10328 KB Output is correct
3 Correct 6 ms 10328 KB Output is correct
4 Runtime error 117 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 81 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 143292 KB Output is correct
2 Correct 157 ms 100176 KB Output is correct
3 Correct 317 ms 96724 KB Output is correct
4 Correct 1217 ms 124280 KB Output is correct
5 Correct 1279 ms 137020 KB Output is correct
6 Correct 214 ms 56384 KB Output is correct
7 Correct 1020 ms 102516 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 7 ms 10328 KB Output is correct
3 Correct 7 ms 10328 KB Output is correct
4 Correct 6 ms 10328 KB Output is correct
5 Runtime error 117 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -