Submission #1232675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232675		poat	The Potion of Great Power (CEOI20_potion)	C++17	17 / 100	3059 ms	93276 KiB

potion

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

const int N = 1e5 + 10, C = 50;

int n, D, H[N], U;
vector<pair<int, int>> Q[N];
vector<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[]) 
{    
    U = u;
    for(int i = 0; i < u; i++)
    {
        Q[AA[i]].push_back({i + 1, BB[i]});
        Q[BB[i]].push_back({i + 1, AA[i]});
    }

    for(int i = 0; i < n; i++)
    {
        set<int> F;
        for(int j = 0; j < Q[i].size(); j++)
        {
            if(j % C == 0)
                S[i].push_back(F);

            if(F.find(Q[i][j].second) != F.end())
                F.erase(Q[i][j].second);
            else
                F.insert(Q[i][j].second);
        }

        if(S[i].empty())
            S[i].push_back(F);
    }


    // for(int i = 0; i < n; i++)
    // {
    //     cout << i << " ==\n";
    //     for(auto j : Q[i])
    //         cout << j.first << ' ' << j.second << "\n";
    //     cout << "\n";
    // }
    // exit(0);

}

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

    int l = 0, r = U;
    while(r - l > 1)
    {
        int m = (l + r) / 2;
        if(m * C - 1 > Q[x].size() || Q[x][m * C - 1].first > v)
            r = m;
        else
            l = m;
    }

    
    for(auto i : S[x][l])
        S1.insert(i);
    
        
    for(int i = l * C; i < Q[x].size(); i++)
    {
        if(Q[x][i].first > v)
            break;

        if(S1.find(Q[x][i].second) == S1.end())
            S1.insert(Q[x][i].second);
        else
            S1.erase(Q[x][i].second);
    }


    l = 0, r = U;
    while(r - l > 1)
    {
        int m = (l + r) / 2;
        if(m * C - 1 > Q[y].size() || Q[y][m * C - 1].first > v)
            r = m;
        else
            l = m;
    }

    for(auto i : S[y][l])
        S2.insert(i);

    for(int i = l * C; i < Q[y].size(); i++)
    {
        if(Q[y][i].first > v)
            break;
            
        if(S2.find(Q[y][i].second) == S2.end())
            S2.insert(Q[y][i].second);
        else
            S2.erase(Q[y][i].second);
    }

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

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

    return res; 
}       

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