Submission #1230813

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

potion

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

const int N = 2e5 + 100;

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

void init(int NN, int DD, int HH[]) {
    n = NN;
    D = DD;
    for(int i = 0; i < n; i++)
        H[i] = HH[i];
}

vector<pair<int, int>> t[N];

void upd(int x, int l, int r, int tl, int tr, int a, int b)
{
    // cout << x << ' ' << l << ' ' << r << ' ' << tl << ' ' << tr << ' ' << a << ' ' << b << '\n';
    // getchar();

    if(tl <= l && tr >= r)
    {
        t[x].push_back({a, b});
        t[x].push_back({b, a});
        return;
    }

    if(tl > r || tr < l)
        return;
    
    int m = (l + r) / 2;
    upd(x * 2, l, m, tl, tr, a, b);
    upd(x * 2 + 1, m + 1, r, tl, tr, a, b);
}

vector<int> V;
void add(int x, int a)
{
    int ind = lower_bound(t[x].begin(), t[x].end(), make_pair(a, 0)) - t[x].begin();
    for(int i = ind; i < t[x].size(); i++)
    {
        if(t[x][i].first != a)
            break;
        V.push_back(H[t[x][i].second]);
    }   
}

void get(int x, int l, int r, int ind, int a)
{
    add(x, a);

    if(l == r)
        return;
    
    int m = (l + r) / 2;
    if(ind <= m)
        get(x * 2, l, m, ind, a);
    else
        get(x * 2 + 1, m + 1, r, ind, a);
}

void out(int x, int l, int r)
{
    cout << l << ' ' << r << " == " << '\n';
    for(auto i : t[x])
        cout << i.first << ' ' << i.second << '\n';
    cout << "\n\n";

    if(l == r)
        return;

    int m = (l + r) / 2;
    out(x * 2, l, m);
    out(x * 2 + 1, m + 1, r);
}   

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;

    map<pair<int, int>, int> mp;
    for(int i = 1; i <= u; i++)
    {
        if(mp[{A[i], B[i]}] != 0)
        {
            int ind = mp[{A[i], B[i]}];
            upd(1, 1, u, ind, i, A[i], B[i]);
            mp[{A[i], B[i]}] = mp[{B[i], A[i]}] = 0;
        }
        else
            mp[{A[i], B[i]}] = mp[{B[i], A[i]}] = i;
    }
    for(auto i : mp)
    {
        if(i.second == 0 || i.first.first > i.first.second)
            continue;
        upd(1, 1, u, i.second, u, i.first.first, i.first.second);
    }

    for(int i = 1; i <= u * 4; i++)
        sort(t[i].begin(), t[i].end());
}

int question(int x, int y, int v) {
    
    vector<int> v1, v2;

    get(1, 1, U, v, x);
    v1 = V;
    V.clear();
    
    // for(auto i : v1)
    //     cout << i << " ";
    // cout << "\n";
    // exit(0);

    
    get(1, 1, U, v, y);
    v2 = V;
    V.clear();

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());

    if(v1.empty() || v2.empty())
        return -1;

    int res = 1e9;
    for(auto i : v1)
    {
        int 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