oj.uz

Submission #866151

# Submission time Handle Problem Language Result Execution time Memory
866151 2023-10-25T13:22:14 Z danikoynov The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 2358 ms 86480 KB 
#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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20824 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 21332 KB Output is correct
2 Correct 6 ms 21080 KB Output is correct
3 Correct 6 ms 21080 KB Output is correct
4 Correct 14 ms 21628 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 885 ms 85880 KB Output is correct
2 Correct 810 ms 85812 KB Output is correct
3 Correct 315 ms 45904 KB Output is correct
4 Correct 1577 ms 77020 KB Output is correct
5 Correct 1004 ms 85648 KB Output is correct
6 Correct 2320 ms 69508 KB Output is correct
7 Correct 877 ms 69612 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 856 ms 86480 KB Output is correct
2 Correct 1050 ms 56384 KB Output is correct
3 Correct 1063 ms 69468 KB Output is correct
4 Correct 1400 ms 69852 KB Output is correct
5 Correct 914 ms 85808 KB Output is correct
6 Correct 1418 ms 69428 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 24152 KB Output is correct
2 Correct 111 ms 22872 KB Output is correct
3 Correct 121 ms 22104 KB Output is correct
4 Correct 578 ms 23432 KB Output is correct
5 Correct 598 ms 24152 KB Output is correct
6 Correct 141 ms 23896 KB Output is correct
7 Correct 455 ms 22616 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20824 KB Output is correct
2 Correct 6 ms 21332 KB Output is correct
3 Correct 6 ms 21080 KB Output is correct
4 Correct 6 ms 21080 KB Output is correct
5 Correct 14 ms 21628 KB Output is correct
6 Correct 885 ms 85880 KB Output is correct
7 Correct 810 ms 85812 KB Output is correct
8 Correct 315 ms 45904 KB Output is correct
9 Correct 1577 ms 77020 KB Output is correct
10 Correct 1004 ms 85648 KB Output is correct
11 Correct 2320 ms 69508 KB Output is correct
12 Correct 877 ms 69612 KB Output is correct
13 Correct 856 ms 86480 KB Output is correct
14 Correct 1050 ms 56384 KB Output is correct
15 Correct 1063 ms 69468 KB Output is correct
16 Correct 1400 ms 69852 KB Output is correct
17 Correct 914 ms 85808 KB Output is correct
18 Correct 1418 ms 69428 KB Output is correct
19 Correct 94 ms 24152 KB Output is correct
20 Correct 111 ms 22872 KB Output is correct
21 Correct 121 ms 22104 KB Output is correct
22 Correct 578 ms 23432 KB Output is correct
23 Correct 598 ms 24152 KB Output is correct
24 Correct 141 ms 23896 KB Output is correct
25 Correct 455 ms 22616 KB Output is correct
26 Correct 804 ms 53828 KB Output is correct
27 Correct 1483 ms 69800 KB Output is correct
28 Correct 1665 ms 82452 KB Output is correct
29 Correct 1515 ms 77300 KB Output is correct
30 Correct 2358 ms 69836 KB Output is correct
31 Correct 1912 ms 56064 KB Output is correct
32 Correct 2234 ms 69764 KB Output is correct