oj.uz

Submission #971942

# Submission time Handle Problem Language Result Execution time Memory
971942 2024-04-29T14:19:54 Z marvinthang The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2299 ms 31572 KB 
/*************************************
*    author: marvinthang             *
*    created: 29.04.2024 20:59:58    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

int N;
vector <int> H;
vector <vector <vector <pair <int, int>>>> events;

void init(int n, int D, int _H[]) {
    N = n;
    H = vector<int>(_H, _H + N);
    events.resize(N);
}

void curseChanges(int U, int A[], int B[]) {
    REP(d, U) {
        auto add_edge = [&] (int u, int v) {
            for (auto &vec: events[u]) if (vec.back().se == v) return void(vec.emplace_back(d + 1, -1));
            for (auto &vec: events[u]) if (vec.back().se == -1) return void(vec.emplace_back(d + 1, v));
            events[u].push_back(vector{pair{d + 1, v}});
        };
        add_edge(A[d], B[d]);
        add_edge(B[d], A[d]);
    }
}

int question(int x, int y, int v) {
    auto get_adj = [&] (int u) {
        vector <int> res;
        for (const auto &vec: events[u]) {
            if (vec[0].fi > v) break;
            int p = lower_bound(ALL(vec), pair{v + 1, -1}) - vec.begin() - 1;
            if (vec[p].se != -1) res.push_back(H[vec[p].se]);
        }
        sort(ALL(res));
        return res;
    };
    vector <int> a = get_adj(x), b = get_adj(y);
    int res = 1e9;
    int i = 0;
    for (int h: a) {
        while (i < (int) b.size() && b[i] < h) ++i;
        if (i < (int) b.size()) res = min(res, abs(h - b[i]));
        if (i) res = min(res, abs(h - b[i - 1]));
    }
    return res;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 10 ms 4028 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 31088 KB Output is correct
2 Correct 234 ms 31468 KB Output is correct
3 Correct 116 ms 10528 KB Output is correct
4 Correct 1174 ms 16056 KB Output is correct
5 Correct 427 ms 29792 KB Output is correct
6 Correct 2261 ms 16324 KB Output is correct
7 Correct 408 ms 16616 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 31572 KB Output is correct
2 Correct 1282 ms 12584 KB Output is correct
3 Correct 730 ms 16740 KB Output is correct
4 Correct 1295 ms 16452 KB Output is correct
5 Correct 309 ms 30600 KB Output is correct
6 Correct 1370 ms 16512 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2388 KB Output is correct
2 Correct 59 ms 1120 KB Output is correct
3 Correct 123 ms 1116 KB Output is correct
4 Correct 609 ms 1564 KB Output is correct
5 Correct 560 ms 2240 KB Output is correct
6 Correct 67 ms 1880 KB Output is correct
7 Correct 623 ms 1112 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 10 ms 4028 KB Output is correct
6 Correct 263 ms 31088 KB Output is correct
7 Correct 234 ms 31468 KB Output is correct
8 Correct 116 ms 10528 KB Output is correct
9 Correct 1174 ms 16056 KB Output is correct
10 Correct 427 ms 29792 KB Output is correct
11 Correct 2261 ms 16324 KB Output is correct
12 Correct 408 ms 16616 KB Output is correct
13 Correct 232 ms 31572 KB Output is correct
14 Correct 1282 ms 12584 KB Output is correct
15 Correct 730 ms 16740 KB Output is correct
16 Correct 1295 ms 16452 KB Output is correct
17 Correct 309 ms 30600 KB Output is correct
18 Correct 1370 ms 16512 KB Output is correct
19 Correct 36 ms 2388 KB Output is correct
20 Correct 59 ms 1120 KB Output is correct
21 Correct 123 ms 1116 KB Output is correct
22 Correct 609 ms 1564 KB Output is correct
23 Correct 560 ms 2240 KB Output is correct
24 Correct 67 ms 1880 KB Output is correct
25 Correct 623 ms 1112 KB Output is correct
26 Correct 643 ms 13456 KB Output is correct
27 Correct 1109 ms 16672 KB Output is correct
28 Correct 1198 ms 24952 KB Output is correct
29 Correct 1079 ms 16076 KB Output is correct
30 Correct 2299 ms 16540 KB Output is correct
31 Correct 2223 ms 12264 KB Output is correct
32 Correct 2125 ms 16328 KB Output is correct