Submission #866151

#	Time	Username	Problem	Language	Result	Execution time	Memory
866151		danikoynov	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	2358 ms	86480 KiB

potion

#include<bits/stdc++.h>

using namespace std;
    


const int maxn = 2e5 + 10;
int n, h[maxn];

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



vector < pair < int, int > > tree[4 * maxn];
void update_range(int root, int left, int right, int qleft, int qright, pair < int, int > tie)
{
    //if (root == 1)
      //  cout << qleft << " " << qright << " " << tie.first << " " << tie.second << endl;
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        tree[root].push_back(tie);
        return;
    }

    int mid = (left + right) / 2;

    update_range(root * 2, left, mid, qleft, qright, tie);
    update_range(root * 2 + 1, mid + 1, right, qleft, qright, tie);
}


//unordered_map < int, int > st[4 * maxn];
void build_tree(int root, int left, int right)
{
    
    sort(tree[root].begin(), tree[root].end());

    /**for (int i = 0; i < tree[root].size(); i ++)
    {
        if (i == 0 || tree[root][i].first != tree[root][i - 1].first)
            st[root][tree[root][i].first] = i;
    }*/

    if (left == right)
        return;

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);


}
pair < int, int > edge[maxn];

int u;

map < pair < int, int >, int > act;

void curseChanges(int U, int A[], int B[]) 
{
    u = U;
    for (int i = 0; i < U; i ++) 
    {
        edge[i] = {A[i], B[i]};
    }
    

    for (int j = 0; j < U; j ++)
    {   
        int a = edge[j].first, b = edge[j].second;
        pair < int, int > lf = {a, b}, rf = {b, a};

        if (act[lf] == 0)
        {
            act[lf] = j + 1;
        }
        else
        {
            update_range(1, 0, U, act[lf], j, lf);
            act[lf] = 0;
        }

        if (act[rf] == 0)
        {
            act[rf] = j + 1;
        }
        else
        {
            update_range(1, 0, U, act[rf], j, rf);
            act[rf] = 0;
        }
    }   
    
    for (auto it : act)
    {
        if (it.second == 0)
            continue;
        update_range(1, 0, U, it.second, U, it.first);
    }
    build_tree(1, 0, U);
    ///exit(0);

}


vector < int > my_set;

void query(int root, int left, int right, int pos, int val)
{
    int lf = 0, rf = (int)(tree[root].size()) - 1;
    while(lf <= rf)
    {
        int mf = (lf + rf) / 2;
        if (tree[root][mf].first < val)
            lf = mf + 1;
        else
            rf = mf - 1;
    }
    int pt = lf;
    while(pt < tree[root].size() && tree[root][pt].first == val)
    {
        
        my_set.push_back(tree[root][pt].second);
        pt ++;
    }
    if (left == right)
        return;

    int mid = (left + right) / 2;
    if (pos <= mid)
        query(root * 2, left, mid, pos, val);
    else
        query(root * 2 + 1, mid + 1, right, pos, val);
}
int question(int x, int y, int v) 
{
    vector < int > hx, hy;
    my_set.clear();
    query(1, 0, u, v, x);
    for (int cur : my_set)
        hx.push_back(h[cur]);
    
    my_set.clear();
    query(1, 0, u, v, y);
    for (int cur : my_set)
        hy.push_back(h[cur]);
    ///cout << hx.size() << " : " << hy.size() << endl;
    sort(hx.begin(), hx.end());
    sort(hy.begin(), hy.end());
    
    int ans = 1e9;
    int pt = 0;
    for (int i = 0; i < hx.size(); i ++)
    {
        while(pt < hy.size() && hy[pt] <= hx[i])
            pt ++;

        if (pt != 0)
            ans = min(ans, abs(hx[i] - hy[pt - 1]));
        if (pt != hy.size())
            ans = min(ans, abs(hx[i] - hy[pt]));
    }
    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 5 5
*/

Compilation message (stderr)

potion.cpp: In function 'void query(int, int, int, int, int)':
potion.cpp:130:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     while(pt < tree[root].size() && tree[root][pt].first == val)
      |           ~~~^~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for (int i = 0; i < hx.size(); i ++)
      |                     ~~^~~~~~~~~~~
potion.cpp:165:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         while(pt < hy.size() && hy[pt] <= hx[i])
      |               ~~~^~~~~~~~~~~
potion.cpp:170:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |         if (pt != hy.size())
      |             ~~~^~~~~~~~~~~~

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