oj.uz

Submission #900503

# Submission time Handle Problem Language Result Execution time Memory
900503 2024-01-08T11:32:59 Z Dec0Dedd The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 1804 ms 86432 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 8e5+10;
const int INF = 1e9;

int n, d, h[N], a[N], b[N], c;
vector<pii> T[N];

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

void add(int v, int l, int r, int ql, int qr, int x, int y) {
    if (l > qr || r < ql) return;
    if (l >= ql && r <= qr) {
        T[v].push_back({x, h[y]});
        T[v].push_back({y, h[x]});
        return;
    } int m=(l+r)/2;
    add(2*v, l, m, ql, qr, x, y), add(2*v+1, m+1, r, ql, qr, x, y);
}

void curseChanges(int sz, int _a[], int _b[]) {
    c=sz;

    map<pii, vector<int>> idx;
    for (int i=1; i<=c; ++i) {
        a[i]=_a[i-1], b[i]=_b[i-1];
        if (a[i] > b[i]) swap(a[i], b[i]);
        idx[{a[i], b[i]}].push_back(i);
    }

    for (auto u : idx) {
        u.second.push_back(c+1);
        int sz=u.second.size();

        // [x0, x1, ..., xn]
        for (int i=0; i+1<sz; i+=2) {
            add(1, 1, c, u.second[i], u.second[i+1]-1, u.first.first, u.first.second);
        }
    }

    for (int i=0; i<N; ++i) sort(T[i].begin(), T[i].end());
}

void dfs(int v, int l, int r, int p, int x, vector<int> *h) {
    int i=upper_bound(T[v].begin(), T[v].end(), make_pair(x, -1))-T[v].begin();
    for (int j=i; j<(int)T[v].size(); ++j) {
        if (T[v][j].first != x) break;
        h->push_back(T[v][j].second);
    }

    if (l == r) return;
    int m=(l+r)/2;
    if (p <= m) dfs(2*v, l, m, p, x, h);
    else dfs(2*v+1, m+1, r, p, x, h);
}

int fnd(vector<int> a, vector<int> b) {
    if (a.empty() || b.empty()) return INF;
    int ptr=0, ans=INF;

    for (auto u : a) {
        while (ptr < (int)b.size()) {
            if (b[ptr] <= u) ++ptr;
            else break;
        }

        ans=min(ans, abs(u-b[min((int)b.size()-1, ptr)]));
        if (ptr > 0) ans=min(ans, abs(u-b[ptr-1]));
    } return ans;
}

int question(int x, int y, int v) {
    vector<int> hx, hy;
    dfs(1, 1, c, v, x, &hx);
    dfs(1, 1, c, v, y, &hy);
    sort(hx.begin(), hx.end()), sort(hy.begin(), hy.end());
    return fnd(hx, hy);
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25176 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25432 KB Output is correct
2 Correct 9 ms 25472 KB Output is correct
3 Correct 10 ms 25432 KB Output is correct
4 Correct 21 ms 25624 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 821 ms 86204 KB Output is correct
2 Correct 770 ms 86244 KB Output is correct
3 Correct 303 ms 50492 KB Output is correct
4 Correct 1310 ms 78836 KB Output is correct
5 Correct 857 ms 85852 KB Output is correct
6 Correct 1804 ms 72108 KB Output is correct
7 Correct 721 ms 72028 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 86432 KB Output is correct
2 Correct 784 ms 59780 KB Output is correct
3 Correct 829 ms 72052 KB Output is correct
4 Correct 999 ms 72024 KB Output is correct
5 Correct 781 ms 86248 KB Output is correct
6 Correct 1044 ms 72280 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 27992 KB Output is correct
2 Correct 112 ms 27224 KB Output is correct
3 Correct 120 ms 26456 KB Output is correct
4 Correct 492 ms 27660 KB Output is correct
5 Correct 455 ms 27736 KB Output is correct
6 Correct 143 ms 27992 KB Output is correct
7 Correct 401 ms 26988 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25176 KB Output is correct
2 Correct 9 ms 25432 KB Output is correct
3 Correct 9 ms 25472 KB Output is correct
4 Correct 10 ms 25432 KB Output is correct
5 Correct 21 ms 25624 KB Output is correct
6 Correct 821 ms 86204 KB Output is correct
7 Correct 770 ms 86244 KB Output is correct
8 Correct 303 ms 50492 KB Output is correct
9 Correct 1310 ms 78836 KB Output is correct
10 Correct 857 ms 85852 KB Output is correct
11 Correct 1804 ms 72108 KB Output is correct
12 Correct 721 ms 72028 KB Output is correct
13 Correct 730 ms 86432 KB Output is correct
14 Correct 784 ms 59780 KB Output is correct
15 Correct 829 ms 72052 KB Output is correct
16 Correct 999 ms 72024 KB Output is correct
17 Correct 781 ms 86248 KB Output is correct
18 Correct 1044 ms 72280 KB Output is correct
19 Correct 93 ms 27992 KB Output is correct
20 Correct 112 ms 27224 KB Output is correct
21 Correct 120 ms 26456 KB Output is correct
22 Correct 492 ms 27660 KB Output is correct
23 Correct 455 ms 27736 KB Output is correct
24 Correct 143 ms 27992 KB Output is correct
25 Correct 401 ms 26988 KB Output is correct
26 Correct 663 ms 56944 KB Output is correct
27 Correct 1116 ms 72600 KB Output is correct
28 Correct 1296 ms 83400 KB Output is correct
29 Correct 1199 ms 78744 KB Output is correct
30 Correct 1766 ms 72260 KB Output is correct
31 Correct 1475 ms 59196 KB Output is correct
32 Correct 1635 ms 72368 KB Output is correct