Submission #1231033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231033		poat	The Potion of Great Power (CEOI20_potion)	C++17	0 / 100	28 ms	13804 KiB

potion

#include<bits/stdc++.h>
// #include "grader.cpp"
using namespace std;

const int N = 2e5 + 100, C = 500;

int n, D, H[N];
int U, A[N], B[N];

vector<int> vec[10][10];
set<int> S[N];


void init(int NN, int DD, int HH[]) 
{
    n = NN;
    D = DD;
    for(int i = 0; i < n; i++)
        H[i] = HH[i];
}
    
    
void curseChanges(int u, int AA[], int BB[]) 
{    
    for(int i = 0; i < u; i++)
    {
        A[i + 1] = AA[i];
        B[i + 1] = BB[i];
    }
    U = u;


    for(int i = 1; i <= u; i++)
    {
        int a = A[i], b = B[i];
        if(S[a].find(b) != S[a].end())
        {
            S[a].erase(b);
            S[b].erase(a);
        }
        else
        {
            S[a].insert(b);
            S[b].insert(a);
        }

        if(i % C == 0)
        {
            int ind = i / C;
            for(int j = 0; j < n; j++)
            {
                for(auto h : S[j])  
                    vec[ind][j].push_back(h);
            }
        }
    }

    // for(int i = 1; i <= 3; i++)
    // {
    //     cout << i << " == \n";
    //     for(int j = 0; j < n; j++)
    //     {
    //         cout << j << " == ";
    //         for(auto h : vec[i][j])
    //             cout << h << ' ';
    //         cout << '\n';
    //     }
    //     cout << '\n';
    // }
    // exit(0);
}

set<int> S1, S2;
vector<int> V1, V2;
int question(int x, int y, int v) 
{
    S1.clear();
    S2.clear();
    V1.clear();
    V2.clear();

    int ind = (v / C);

    for(auto i : vec[ind][x])
        S1.insert(i);
    for(auto i : vec[ind][y])
        S2.insert(i);

    ind *= C;

    for(int i = ind + 1; i <= v; i++)
    {
        if(A[i] == x || B[i] == x)
        {
            int k = (A[i] == x ? B[i] : A[i]);
            if(S1.find(k) != S1.end())
                S1.erase(k);
            else
                S1.insert(k);
        }
        if(A[i] == y || B[i] == y)
        {
            int k = (A[i] == y ? B[i] : A[i]);
            if(S2.find(k) != S2.end())
                S2.erase(k);
            else
                S2.insert(k);
        }
    }


    for(auto i : S1)
        V1.push_back(H[i]);
    for(auto i : S2)
        V2.push_back(H[i]);

    int res = 1e9;
    for(auto i : V1)
    {
        ind = lower_bound(V2.begin(), V2.end(), i) - V2.begin();
        if(ind != V2.size())
            res = min(res, V2[ind] - i);
        if(ind)
            res = min(res, i - V2[ind - 1]);
    }

    return res;      
}   

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