oj.uz

Submission #631667

# Submission time Handle Problem Language Result Execution time Memory
631667 2022-08-18T12:00:55 Z abc864197532 The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2292 ms 73108 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
    vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
    vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
    vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
    vvv() {}
};
#ifdef Doludu
#define test(args...) abc("[" + string(#args) + "]", args)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(args...) void(0)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
const int mod = 1e9 + 7, N = 200005, logC = 30, K = 450;

vector <pii> tree[N << 1];

void add(int l, int r, int u, int v) {
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1)
            tree[l++].eb(u, v);
        if (r & 1)
            tree[--r].eb(u, v);
    }
}

int u_nei[N], v_nei[N], h[N], sz1, sz2;

void query(int day, int u, int v) {
    sz1 = sz2 = 0;
    for (day += N; day > 0; day >>= 1) {
        for (auto it = lower_bound(all(tree[day]), mp(u, -1)); it != tree[day].end() && it->X == u; ++it) {
            u_nei[sz1++] = h[it->Y];
        }
        for (auto it = lower_bound(all(tree[day]), mp(v, -1)); it != tree[day].end() && it->X == v; ++it) {
            v_nei[sz2++] = h[it->Y];
        }
    }
}

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

void curseChanges(int m, int a[], int b[]) {
    map <pii, int> edge;
    for (int i = 1; i <= m; ++i) {
        int u = a[i - 1], v = b[i - 1];
        if (u > v)
            swap(u, v);
        if (edge.count({u, v})) {
            add(edge[{u, v}], i, u, v);
            add(edge[{u, v}], i, v, u);
            edge.erase({u, v});
        } else {
            edge[{u, v}] = i;
        }
    }
    for (auto A : edge) {
        add(A.Y, m + 1, A.X.X, A.X.Y);
        add(A.Y, m + 1, A.X.Y, A.X.X);
    }
    for (int i = 0; i < N << 1; ++i)
        sort(all(tree[i]));
}

int question(int u, int v, int d) {
    query(d, u, v);
    if (!sz1 || !sz2) {
        return 1000000000;
    } else {
        int ans = 1000000000;
        sort(u_nei, u_nei + sz1), sort(v_nei, v_nei + sz2);
        for (int i = 0, j = 0; i < sz1; ++i) {
            while (j < sz2 && v_nei[j] < u_nei[i])
                j++;
            if (j < sz2)
                ans = min(ans, abs(u_nei[i] - v_nei[j]));
            if (j) 
                ans = min(ans, abs(u_nei[i] - v_nei[j - 1]));
        }
        return ans;
    }
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9956 KB Output is correct
2 Correct 8 ms 9936 KB Output is correct
3 Correct 8 ms 9956 KB Output is correct
4 Correct 20 ms 10744 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 73108 KB Output is correct
2 Correct 828 ms 73084 KB Output is correct
3 Correct 307 ms 33772 KB Output is correct
4 Correct 1480 ms 60880 KB Output is correct
5 Correct 921 ms 72296 KB Output is correct
6 Correct 2292 ms 54740 KB Output is correct
7 Correct 756 ms 54888 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 930 ms 73108 KB Output is correct
2 Correct 857 ms 38288 KB Output is correct
3 Correct 993 ms 54764 KB Output is correct
4 Correct 1245 ms 54704 KB Output is correct
5 Correct 1050 ms 72716 KB Output is correct
6 Correct 1329 ms 54820 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 12612 KB Output is correct
2 Correct 129 ms 11060 KB Output is correct
3 Correct 146 ms 10740 KB Output is correct
4 Correct 623 ms 12072 KB Output is correct
5 Correct 619 ms 12268 KB Output is correct
6 Correct 174 ms 12496 KB Output is correct
7 Correct 462 ms 11028 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 9 ms 9956 KB Output is correct
3 Correct 8 ms 9936 KB Output is correct
4 Correct 8 ms 9956 KB Output is correct
5 Correct 20 ms 10744 KB Output is correct
6 Correct 787 ms 73108 KB Output is correct
7 Correct 828 ms 73084 KB Output is correct
8 Correct 307 ms 33772 KB Output is correct
9 Correct 1480 ms 60880 KB Output is correct
10 Correct 921 ms 72296 KB Output is correct
11 Correct 2292 ms 54740 KB Output is correct
12 Correct 756 ms 54888 KB Output is correct
13 Correct 930 ms 73108 KB Output is correct
14 Correct 857 ms 38288 KB Output is correct
15 Correct 993 ms 54764 KB Output is correct
16 Correct 1245 ms 54704 KB Output is correct
17 Correct 1050 ms 72716 KB Output is correct
18 Correct 1329 ms 54820 KB Output is correct
19 Correct 106 ms 12612 KB Output is correct
20 Correct 129 ms 11060 KB Output is correct
21 Correct 146 ms 10740 KB Output is correct
22 Correct 623 ms 12072 KB Output is correct
23 Correct 619 ms 12268 KB Output is correct
24 Correct 174 ms 12496 KB Output is correct
25 Correct 462 ms 11028 KB Output is correct
26 Correct 715 ms 34852 KB Output is correct
27 Correct 1380 ms 54804 KB Output is correct
28 Correct 1713 ms 68084 KB Output is correct
29 Correct 1472 ms 60912 KB Output is correct
30 Correct 2286 ms 54960 KB Output is correct
31 Correct 1771 ms 37336 KB Output is correct
32 Correct 2036 ms 54824 KB Output is correct