oj.uz

Submission #865985

# Submission time Handle Problem Language Result Execution time Memory
865985 2023-10-25T08:57:28 Z boris_mihov The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 1971 ms 44496 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 4 ms 14936 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 13 ms 15736 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 44496 KB Output is correct
2 Correct 243 ms 44308 KB Output is correct
3 Correct 226 ms 20032 KB Output is correct
4 Correct 977 ms 32480 KB Output is correct
5 Correct 363 ms 43332 KB Output is correct
6 Correct 1971 ms 27836 KB Output is correct
7 Correct 334 ms 27064 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 44124 KB Output is correct
2 Correct 828 ms 20584 KB Output is correct
3 Correct 485 ms 27912 KB Output is correct
4 Correct 771 ms 27336 KB Output is correct
5 Correct 284 ms 43696 KB Output is correct
6 Correct 908 ms 27656 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16216 KB Output is correct
2 Correct 48 ms 15800 KB Output is correct
3 Correct 105 ms 15720 KB Output is correct
4 Correct 502 ms 16044 KB Output is correct
5 Correct 473 ms 16320 KB Output is correct
6 Correct 60 ms 16216 KB Output is correct
7 Correct 487 ms 15424 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Correct 4 ms 14936 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 13 ms 15736 KB Output is correct
6 Correct 239 ms 44496 KB Output is correct
7 Correct 243 ms 44308 KB Output is correct
8 Correct 226 ms 20032 KB Output is correct
9 Correct 977 ms 32480 KB Output is correct
10 Correct 363 ms 43332 KB Output is correct
11 Correct 1971 ms 27836 KB Output is correct
12 Correct 334 ms 27064 KB Output is correct
13 Correct 227 ms 44124 KB Output is correct
14 Correct 828 ms 20584 KB Output is correct
15 Correct 485 ms 27912 KB Output is correct
16 Correct 771 ms 27336 KB Output is correct
17 Correct 284 ms 43696 KB Output is correct
18 Correct 908 ms 27656 KB Output is correct
19 Correct 30 ms 16216 KB Output is correct
20 Correct 48 ms 15800 KB Output is correct
21 Correct 105 ms 15720 KB Output is correct
22 Correct 502 ms 16044 KB Output is correct
23 Correct 473 ms 16320 KB Output is correct
24 Correct 60 ms 16216 KB Output is correct
25 Correct 487 ms 15424 KB Output is correct
26 Correct 468 ms 20904 KB Output is correct
27 Correct 809 ms 27768 KB Output is correct
28 Correct 902 ms 37512 KB Output is correct
29 Correct 816 ms 32220 KB Output is correct
30 Correct 1722 ms 27248 KB Output is correct
31 Correct 1653 ms 20456 KB Output is correct
32 Correct 1515 ms 27652 KB Output is correct