oj.uz

Submission #1055828

# Submission time Handle Problem Language Result Execution time Memory
1055828 2024-08-13T05:55:39 Z TAhmed33 The Potion of Great Power (CEOI20_potion) C++17
0 / 100
 183 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
//#include "grader.cpp"
const int MAXN = 1e5 + 25;
const int B = 1000;
int n, d, h[MAXN];
void init(int N, int D, int H[]) {
    n = N; d = D;
    for (int i = 0; i < n; i++) {
        h[i] = H[i];
    }
}
int u, a[MAXN], b[MAXN];
vector <int> adj[MAXN / B + 1][MAXN];
void curseChanges(int U, int A[], int BB[]) {
    u = U;
    for (int i = 0; i < u; i++) {
        a[i] = A[i]; b[i] = BB[i];
    }
    int ptr = 0;
    int cnt = 0;
    set <pair <int, int>> dd;
    for (int i = 0; i < u; i += B) {
        for (auto [x, y] : dd) {
            adj[cnt][x].push_back(y);
            adj[cnt][y].push_back(x);
        }
        for (int j = i; j <= min(u - 1, i + B - 1); j++) {
            if (dd.count({a[j], b[j]})) {
                dd.erase({a[j], b[j]});
            } else {
                dd.insert({a[j], b[j]});
            }
        }
        cnt++;
    }
}

int question (int x, int y, int v) {
    set <int> g, h2;
    for (auto j : adj[v / B][x]) {
        g.insert(j);
    }
    for (auto j : adj[v / B][y]) {
        h2.insert(j);
    }
/*    for (auto j : g) {
        cout << j << " ";
    }
    cout << '\n';
    for (auto j : h2) {
        cout << j << " ";
    }
    cout << '\n';*/
    for (int i = B * (v / B); i < v; i++) {
        if (a[i] == x) {
            if (g.count(b[i])) {
                g.erase(b[i]);
            } else {
                g.insert(b[i]);
            }
        } else if (b[i] == x) {
            if (g.count(a[i])) {
                g.erase(a[i]);
            } else {
                g.insert(a[i]);
            }
        }
        if (a[i] == y) {
            if (h2.count(b[i])) {
                h2.erase(b[i]);
            } else {
                h2.insert(b[i]);
            }
        } else if (b[i] == y) {
            if (h2.count(a[i])) {
                h2.erase(a[i]);
            } else {
                h2.insert(a[i]);
            }
        }
    }
/*    for (auto j : g) {
        cout << j << " ";
    }
    cout << '\n';
    for (auto j : h2) {
        cout << j << " ";
    }
    cout << '\n';*/
    multiset <int> xx, yy;
    for (auto j : g) {
        xx.insert(h[j]);
    }
    for (auto j : h2) {
        yy.insert(h[j]);
    }
/*    for (auto j : xx) {
        cout << j << " ";
    }
    cout << '\n';
    for (auto j : yy) {
        cout << j << " ";
    }
    cout << '\n';*/
    int mn = 1e9;
    for (auto j : xx) {
        auto k = yy.lower_bound(j);
        if (k != yy.end()) {
            mn = min(mn, (*k) - j);
        }
        if (k != yy.begin()) {
            k--;
            mn = min(mn, j - *k);
        }
    }
    return mn;
}

Compilation message

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:21:9: warning: unused variable 'ptr' [-Wunused-variable]
   21 |     int ptr = 0;
      |         ^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 237536 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 237548 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 145 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 183 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 239952 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 237536 KB Output is correct
2 Incorrect 77 ms 237548 KB Incorrect
3 Halted 0 ms 0 KB -