oj.uz

Submission #900497

# Submission time Handle Problem Language Result Execution time Memory
900497 2024-01-08T11:25:22 Z Dec0Dedd The Potion of Great Power (CEOI20_potion) C++14
38 / 100
 1231 ms 262144 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;
map<int, vector<int>> 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][x].push_back(h[y]);
        T[v][y].push_back(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);
        }
    }
}

void dfs(int v, int l, int r, int p, int x, vector<int> *h) {
    for (auto u : T[v][x]) h->push_back(u);
    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 12 ms 43608 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 46052 KB Output is correct
2 Correct 16 ms 45948 KB Output is correct
3 Correct 16 ms 45940 KB Output is correct
4 Correct 29 ms 46940 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1231 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1211 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1042 ms 142380 KB Output is correct
2 Correct 493 ms 88756 KB Output is correct
3 Correct 280 ms 63044 KB Output is correct
4 Correct 955 ms 81260 KB Output is correct
5 Correct 1179 ms 98544 KB Output is correct
6 Correct 779 ms 112072 KB Output is correct
7 Correct 662 ms 67604 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 43608 KB Output is correct
2 Correct 17 ms 46052 KB Output is correct
3 Correct 16 ms 45948 KB Output is correct
4 Correct 16 ms 45940 KB Output is correct
5 Correct 29 ms 46940 KB Output is correct
6 Runtime error 1231 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -