Submission #865985

#	Time	Username	Problem	Language	Result	Execution time	Memory
865985		boris_mihov	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	1971 ms	44496 KiB

potion

#include <algorithm>
#include <iostream>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>
#include <map>

typedef long long llong;
const int MAXN = 200000 + 10;
const int INF  = 1e9;

struct Edge
{
    int to;
    int l, r;
};

int n;
int h[MAXN];
std::vector <Edge> g[MAXN]; 
std::map <int,int> active[MAXN];

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

void addEdge(int u, int v, int d)
{
    if (active[u].count(v))
    {
        g[u][active[u][v]].r = d;
        active[u].erase(active[u].find(v));
    } else
    {
        g[u].push_back({v, d + 1, MAXN});
        active[u][v] = g[u].size() - 1;
    }
}

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

int question(int x, int y, int day) 
{
    x++; y++; 
    std::vector <int> a, b;
    for (const Edge &curr: g[x])
    {
        if (curr.l <= day && day <= curr.r)
        {
            a.push_back(h[curr.to]);
        }
    }

    for (const Edge &curr: g[y])
    {
        if (curr.l <= day && day <= curr.r)
        {
            b.push_back(h[curr.to]);
        }
    }

    if (a.empty() || b.empty())
    {
        return 1e9;
    }

    int res = 1e9;
    int lPtr = 0, rPtr = 0;
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());

    while (lPtr < a.size() || rPtr < b.size())
    {
        if (lPtr == a.size())
        {
            res = std::min(res, b[rPtr] - a.back());
            break;
        }

        if (rPtr == b.size())
        {
            res = std::min(res, a[lPtr] - b.back());
            break;
        }

        res = std::min(res, abs(a[lPtr] - b[rPtr]));
        if (a[lPtr] < b[rPtr]) lPtr++;
        else rPtr++;
    }

    return res;
}

/*
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
3 0 8
0 5 5
3 0 11
*/

Compilation message (stderr)

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:88:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     while (lPtr < a.size() || rPtr < b.size())
      |            ~~~~~^~~~~~~~~~
potion.cpp:88:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     while (lPtr < a.size() || rPtr < b.size())
      |                               ~~~~~^~~~~~~~~~
potion.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         if (lPtr == a.size())
      |             ~~~~~^~~~~~~~~~~
potion.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         if (rPtr == b.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