Submission #551435

#	Time	Username	Problem	Language	Result	Execution time	Memory
551435		blue	The Potion of Great Power (CEOI20_potion)	C++17	0 / 100	1073 ms	262144 KiB

potion

#include <iostream>
#include <vector>
#include <set>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
#define sz(x) int(x.size())

int N;
int D;
vi H;

set<int> edge[100'000];

vi times[100'000];
vvi states[100'000];

void init(int N_, int D_, int H_[]) 
{
    N = N_;
    D = D_;
    H = vi(N);
    for(int i = 0; i < N; i++)
        H[i] = H_[i];

    for(int i = 0; i < N; i++)
    {
        states[i].push_back({});
        times[i].push_back(0);
    }

    // cerr << "done 1\n";
}

bool cmp(int i, int j)
{
    if(H[i] == H[j])
        return i < j;
    else 
        return H[i] < H[j];
}

void insert_neighbor(int ti, int p, int q)
{
    // cerr << "ins " << ti << ' ' << p << ' ' << q << '\n';
    vi newstates;

    bool inserted = 0;

    for(int z : states[p].back())
    {
        if(!inserted && cmp(q, z))
        {
            newstates.push_back(q);
            inserted = 1;
        }

        newstates.push_back(z);
    }

    if(!inserted)
    {
        newstates.push_back(q);
        inserted = 1;
    }

    states[p].push_back(newstates);
    times[p].push_back(ti);

    edge[p].insert(q);
}

void erase_neighbor(int ti, int p, int q)
{
    vi newstates;

    for(int z : states[p].back())
    {
        if(z != q) newstates.push_back(z);
    }

   states[p].push_back(newstates);
   times[p].push_back(ti);

   edge[p].erase(q);
}

void curseChanges(int U, int A[], int B[]) 
{
    // cerr << "curse changes enter\n";
    for(int u = 0; u < U; u++)
    {
        int a = A[u], b = B[u];
        if(edge[a].find(b) == edge[a].end())
        {
            insert_neighbor(u, a, b);
            insert_neighbor(u, b, a);
        }
        else
        {   
            erase_neighbor(u, a, b);
            erase_neighbor(u, b, a);
        }
    }

    // cerr << "done 2\n";

    // for(auto k : states[0])
    //     cerr << sz(k) << ' ';
    // cerr << '\n';

    // cerr << "curse changes exit\n";
}

int question(int x, int y, int v) 
{
    // cerr << "question " << x << ' ' << y << ' ' << v << '\n';
    int xlo = 0, xhi = sz(times[x]) - 1;
    while(xlo != xhi)
    {
        int mid = (xlo + xhi)/2 + 1;
        if(times[x][mid] > v)
            xhi = mid - 1;
        else
            xlo = mid;
    }

    int ylo = 0, yhi = sz(times[y]) - 1;
    while(ylo != yhi)
    {
        int mid = (ylo + yhi)/2 + 1;
        if(times[y][mid] > v)
            yhi = mid - 1;
        else
            ylo = mid;
    }


    vi sx = states[x][xlo];
    vi sy = states[y][ylo];

    // for(int z : sx) cerr << "z = " << z << '\n';
    // for(int z2 : sy) cerr << "z2 = " << z2 << '\n';

    int res = 1'000'000'000;

    int qi = 0;

    // cerr << sz(sx) << ' ' << sz(sy) << '\n';

    if(sx.empty() || sy.empty())
        return 1'000'000'000;
    // cerr << "hello\n";

    for(int p : sx)
    {
        // cerr << "p = " << p << '\n';
        while(qi+1 < sz(sy) && cmp(sy[qi+1], p))
            qi++;

        res = min(res, abs(H[p] - H[sy[qi]]));

        if(qi+1 < sz(sy))
            res = min(res, abs(H[p] - H[sy[qi + 1]]));
    }

    // cerr << "answering\n";

    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