제출 #493022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493022		LittleCube	The Potion of Great Power (CEOI20_potion)	C++14	17 / 100	3093 ms	113412 KiB

potion

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, D, H[100005], U, B, uid[200005], udx;
pii change[200005];
bool block[505][200005];
vector<int> v[100005];
map<int, int> mp[100005];

void init(int n, int d, int h[])
{
    N = n;
    D = d;
    for (int i = 0; i < N; i++)
        H[i] = h[i];
}

void curseChanges(int u, int a[], int b[])
{
    U = u;
    B = sqrt(U);
    for (int i = 0; i < U; i++)
    {
        if (a[i] > b[i])
            swap(a[i], b[i]);
        change[i].F = a[i];
        change[i].S = b[i];
    }
    for (int i = 0; i < U; i++)
        if (mp[a[i]].find(b[i]) != mp[a[i]].end())
            uid[i] = mp[a[i]][b[i]];
        else
        {
            mp[a[i]][b[i]] = uid[i] = i;
            v[a[i]].emplace_back(i);
            v[b[i]].emplace_back(i);
        }
    for (int i = 1, j = 0; j < U; i++)
    {
        for (int k = 0; k < U; k++)
            block[i][k] = block[i - 1][k];
        for (; j < i * B && j < U; j++)
            block[i][uid[j]] ^= 1;
    }
}

int question(int x, int y, int V)
{

    int b = V / B;
    multiset<ll> sx, sy;
    map<int, bool> mx, my;
    for (int i : v[x])
        if (block[b][i])
        {
            if (change[i].F == x)
            {
                sx.insert(H[change[i].S]);
                mx[change[i].S] = 1;
            }
            else
            {
                sx.insert(H[change[i].F]);
                mx[change[i].F] = 1;
            }
        }
    for (int i : v[y])
        if (block[b][i])
        {
            if (change[i].F == y)
            {
                sy.insert(H[change[i].S]);
                my[change[i].S] = 1;
            }
            else
            {
                sy.insert(H[change[i].F]);
                my[change[i].F] = 1;
            }
        }
    for (int i = b * B; i < V; i++)
    {
        if (change[i].S == x)
        {
            mx[change[i].F] ^= 1;
            if (mx[change[i].F])
                sx.insert(H[change[i].F]);
            else
                sx.erase(sx.find(H[change[i].F]));
        }
        if (change[i].S == y)
        {
            my[change[i].F] ^= 1;
            if (my[change[i].F])
                sy.insert(H[change[i].F]);
            else
                sy.erase(sy.find(H[change[i].F]));
        }
        if (change[i].F == x)
        {
            mx[change[i].S] ^= 1;
            if (mx[change[i].S])
                sx.insert(H[change[i].S]);
            else
                sx.erase(sx.find(H[change[i].S]));
        }
        if (change[i].F == y)
        {
            my[change[i].S] ^= 1;
            if (my[change[i].S])
                sy.insert(H[change[i].S]);
            else
                sy.erase(sy.find(H[change[i].S]));
        }
    }
    sy.insert(2e9);
    sy.insert(-2e9);
    ll ans = 1e9;
    for (ll i : sx)
    {
        if (i <= -1.5e9 || i >= 1.5e9)
            continue;
        auto iter = sy.lower_bound(i);
        ans = min({ans, abs(i - *iter), abs(i - *prev(iter))});
    }
    return ans;
}

/*
6 5 11 4
2 42 1000 54 68 234
0 1 2 0 3 4 3 5 3 5 1 3 5 3 0 5 3 0 1 3 3 5
0 3 4 26
3 0 8 0
0 5 5 1000000000
3 0 11 14
*/

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