Submission #1230833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230833		poat	The Potion of Great Power (CEOI20_potion)	C++17	38 / 100	592 ms	34104 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> V1, V2;
vector<int> G1, G2;
void add(int x, int a, int b)
{
    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;
        G1.push_back(t[x][i].second);
        V1.push_back(H[t[x][i].second]);
    }   
    ind = lower_bound(t[x].begin(), t[x].end(), make_pair(b, 0)) - t[x].begin();
    for(int i = ind; i < t[x].size(); i++)
    {
        if(t[x][i].first != b)
            break;
        G2.push_back(t[x][i].second);
        V2.push_back(H[t[x][i].second]);
    }   
    
}

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

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

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 - 1, 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) {
    
    V1.clear();
    V2.clear();
    G1.clear();
    G2.clear();


    get(1, 1, U, v, x, y);
    
    sort(V1.begin(), V1.end());
    sort(V2.begin(), V2.end());

    if(V1.empty() || V2.empty())
        return 1e9;

    long long res = 2e9;
    for(auto i : V1)
    {
        int ind = lower_bound(V2.begin(), V2.end(), i) - V2.begin();

        if(ind != V2.size())
            res = min(res, 1ll * V2[ind] - i);
        if(ind)
            res = min(res, 1ll * i - V2[ind - 1]);
    }

    // cout << res << "\n";
    // for(auto i : V1)
    //     cout << i << " ";
    // cout << '\n';
    // for(auto i : V2)
    //     cout << i << ' ';
    // exit(0);

    return res;
}   

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