oj.uz

Submission #578119

# Submission time Handle Problem Language Result Execution time Memory
578119 2022-06-16T05:13:31 Z tengiz05 The Potion of Great Power (CEOI20_potion) C++17
70 / 100
 3000 ms 139656 KB 
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;

constexpr int N = 1E5 + 5, D = 30;
int h[N], n;
vector<pair<int, int>> mv[N];
vector<set<pair<int, int>>> s[N];

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

void curseChanges(int U, int A[], int B[]) {
    for (int i = 0; i < U; i++) {
        mv[A[i]].emplace_back(i, B[i]);
        mv[B[i]].emplace_back(i, A[i]);
    }
    for (int i = 0; i < n; i++) {
        int z = mv[i].size();
        set<pair<int, int>> v;
        for (int j = 0; j < z; j++) {
            if (j % D == 0) {
                s[i].push_back(v);
            }
            if (v.count({h[mv[i][j].second], mv[i][j].second}))
                v.erase({h[mv[i][j].second], mv[i][j].second});
            else
                v.insert({h[mv[i][j].second], mv[i][j].second});
        }
    }
}

int question(int x, int y, int v) {
    if (v == 0)
        return 1E9;
    int F = lower_bound(mv[x].begin(), mv[x].end(), pair(v, -1)) - mv[x].begin() - 1;
    int S = lower_bound(mv[y].begin(), mv[y].end(), pair(v, -1)) - mv[y].begin() - 1;
    if (F == -1 || S == -1)
        return 1E9;
    set<pair<int, int>> a = s[x][F / D], b = s[y][S / D];
    for (int i = F / D * D; i <= F; i++) {
        int g = mv[x][i].second;
        if (a.count({h[g], g})) {
            a.erase({h[g], g});
        } else {
            a.insert({h[g], g});
        }
    }
    for (int i = S / D * D; i <= S; i++) {
        int g = mv[y][i].second;
        if (b.count({h[g], g})) {
            b.erase({h[g], g});
        } else {
            b.insert({h[g], g});
        }
    }
    vector<pair<int, int>> B(b.begin(), b.end());
    int i = 0;
    int ans = 1E9;
    for (auto [x, y] : a) {
        while (i < int(B.size()) && B[i].first < x)
            i++;
        if (i > 0) {
            ans = min(ans, x - B[i - 1].first);
        }
        if (i < int(B.size())) {
            ans = min(ans, B[i].first - x);
        }
    }
    return ans;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5072 KB Output is correct
2 Correct 4 ms 5072 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 15 ms 5952 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 19472 KB Output is correct
2 Correct 205 ms 19456 KB Output is correct
3 Correct 324 ms 17712 KB Output is correct
4 Correct 1688 ms 89800 KB Output is correct
5 Correct 556 ms 25876 KB Output is correct
6 Correct 2912 ms 130496 KB Output is correct
7 Correct 722 ms 29912 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 19472 KB Output is correct
2 Correct 2357 ms 139656 KB Output is correct
3 Correct 1450 ms 74224 KB Output is correct
4 Correct 2524 ms 130112 KB Output is correct
5 Correct 348 ms 26144 KB Output is correct
6 Correct 2796 ms 130148 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6024 KB Output is correct
2 Correct 173 ms 5584 KB Output is correct
3 Correct 304 ms 5712 KB Output is correct
4 Correct 990 ms 8056 KB Output is correct
5 Correct 911 ms 7504 KB Output is correct
6 Correct 181 ms 5456 KB Output is correct
7 Correct 841 ms 7292 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 4 ms 5072 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 4 ms 5072 KB Output is correct
5 Correct 15 ms 5952 KB Output is correct
6 Correct 207 ms 19472 KB Output is correct
7 Correct 205 ms 19456 KB Output is correct
8 Correct 324 ms 17712 KB Output is correct
9 Correct 1688 ms 89800 KB Output is correct
10 Correct 556 ms 25876 KB Output is correct
11 Correct 2912 ms 130496 KB Output is correct
12 Correct 722 ms 29912 KB Output is correct
13 Correct 175 ms 19472 KB Output is correct
14 Correct 2357 ms 139656 KB Output is correct
15 Correct 1450 ms 74224 KB Output is correct
16 Correct 2524 ms 130112 KB Output is correct
17 Correct 348 ms 26144 KB Output is correct
18 Correct 2796 ms 130148 KB Output is correct
19 Correct 42 ms 6024 KB Output is correct
20 Correct 173 ms 5584 KB Output is correct
21 Correct 304 ms 5712 KB Output is correct
22 Correct 990 ms 8056 KB Output is correct
23 Correct 911 ms 7504 KB Output is correct
24 Correct 181 ms 5456 KB Output is correct
25 Correct 841 ms 7292 KB Output is correct
26 Correct 1115 ms 53040 KB Output is correct
27 Correct 1740 ms 74576 KB Output is correct
28 Correct 1726 ms 65604 KB Output is correct
29 Correct 1681 ms 89680 KB Output is correct
30 Execution timed out 3050 ms 130132 KB Time limit exceeded
31 Halted 0 ms 0 KB -