oj.uz

Submission #900459

# Submission time Handle Problem Language Result Execution time Memory
900459 2024-01-08T10:26:55 Z Dec0Dedd The Potion of Great Power (CEOI20_potion) C++14
0 / 100
 3000 ms 12900 KB 
#include <bits/stdc++.h>

using namespace std;

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

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

int n, d, h[N], a[N], b[N], c;

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

void curseChanges(int sz, int _a[], int _b[]) {
    c=sz;
    for (int i=1; i<=c; ++i) a[i]=_a[i-1], b[i]=_b[i-1];
}

int question(int x, int y, int v) {
    ++v;

    map<int, int> usx, usy;
    for (int i=1; i<=v; ++i) {
        if (a[i] == x) usx[b[i]]^=1;
        else if (b[i] == x) usx[a[i]]^=1;

        if (a[i] == y) usy[b[i]]^=1;
        else if (b[i] == y) usy[a[i]]^=1;
    } usx[x]=usy[y]=0;

    vector<int> hx, hy;
    for (int i=1; i<=v; ++i) {
        if (usx[a[i]]) hx.push_back(h[a[i]]);
        if (usx[b[i]]) hx.push_back(h[b[i]]);
        if (usy[a[i]]) hy.push_back(h[a[i]]);
        if (usy[b[i]]) hy.push_back(h[b[i]]);
    } sort(hx.begin(), hx.end()), sort(hy.begin(), hy.end());

    if (hx.empty() || hy.empty()) return INF;
    int ptr=0, ans=INF;

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

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

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 576 KB Output is correct
2 Incorrect 159 ms 592 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 12900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 12692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3024 ms 1800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 195 ms 576 KB Output is correct
3 Incorrect 159 ms 592 KB Incorrect
4 Halted 0 ms 0 KB -