oj.uz

Submission #972532

# Submission time Handle Problem Language Result Execution time Memory
972532 2024-04-30T14:24:10 Z RaresFelix The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2292 ms 31272 KB 
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
const int MN = 100000;
int n;
int H0[MN];

vector<pair<int, int> > Op[MN];
vi SnapId[MN];
vi Mare[400000]; 
int pma = 0;

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

int rad = 50;

void curseChanges(int U, int A[], int B[]) {
    for(int i = 0; i < U; ++i) {
        Op[A[i]].push_back({i + 1, B[i]});
        Op[B[i]].push_back({i + 1, A[i]});
    }

    set<int> S;
    for(int i = 0; i < n; ++i) {
        S.clear();
        SnapId[i].push_back(pma);
        ++pma;
        for(int j = 0; j < Op[i].size(); ++j) {
            if(j % rad == 0 && j) {
                SnapId[i].push_back(pma);
                Mare[pma].reserve(S.size());
                for(auto it : S) Mare[pma].push_back(it);
                ++pma;
            }
            auto [t, v] = Op[i][j];
            if(S.count(v)) S.erase(v);
            else S.insert(v);
        }
    }
}
const int INF = 1e9;

vi get(int x, int v) {
    int st = 0, dr = int(Op[x].size()) - 1, mij;
    if(Op[x].empty() || Op[x][0].first > v) return vi();
    while(st < dr) {
        mij = (st + dr + 1) / 2;
        if(Op[x][mij].first > v) dr = mij - 1; // e ok asa?
        else st = mij;
    }
    unordered_set<int> Fr;
    for(int i = st / rad * rad; i <= st; ++i) {
        auto [t, v] = Op[x][i];
        if(Fr.count(v)) Fr.erase(v);
        else Fr.insert(v);
    }
    vi Re;
    for(auto it : Mare[SnapId[x][st / rad]]) {
        if(!Fr.count(it))
            Re.push_back(H0[it]);
        else Fr.erase(it);
    }
    for(auto v : Fr) Re.push_back(H0[v]);
    sort(Re.begin(), Re.end());
    return Re;
}

int question(int x, int y, int v) {
    auto VA = get(x, v), VB = get(y, v);
    int pa = 0, pb = 0;
    int re = INF;
    while(pa < VA.size() && pb < VB.size()) {
        re = min(re, abs(VA[pa] - VB[pb]));
        if(VA[pa] < VB[pb]) ++pa;
        else ++pb;
    }
    return re;
}

Compilation message

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:35:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int j = 0; j < Op[i].size(); ++j) {
      |                        ~~^~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:79:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     while(pa < VA.size() && pb < VB.size()) {
      |           ~~~^~~~~~~~~~~
potion.cpp:79:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     while(pa < VA.size() && pb < VB.size()) {
      |                             ~~~^~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14424 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14424 KB Output is correct
2 Correct 5 ms 14424 KB Output is correct
3 Correct 4 ms 14424 KB Output is correct
4 Correct 17 ms 18380 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 25492 KB Output is correct
2 Correct 192 ms 26028 KB Output is correct
3 Correct 247 ms 23624 KB Output is correct
4 Correct 1215 ms 24652 KB Output is correct
5 Correct 454 ms 22156 KB Output is correct
6 Correct 2292 ms 31260 KB Output is correct
7 Correct 535 ms 26492 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 26120 KB Output is correct
2 Correct 1145 ms 30928 KB Output is correct
3 Correct 751 ms 28456 KB Output is correct
4 Correct 1204 ms 30520 KB Output is correct
5 Correct 273 ms 26144 KB Output is correct
6 Correct 1326 ms 30960 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15448 KB Output is correct
2 Correct 134 ms 15248 KB Output is correct
3 Correct 231 ms 15408 KB Output is correct
4 Correct 788 ms 15448 KB Output is correct
5 Correct 754 ms 15600 KB Output is correct
6 Correct 137 ms 14936 KB Output is correct
7 Correct 656 ms 15344 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14424 KB Output is correct
2 Correct 4 ms 14424 KB Output is correct
3 Correct 5 ms 14424 KB Output is correct
4 Correct 4 ms 14424 KB Output is correct
5 Correct 17 ms 18380 KB Output is correct
6 Correct 194 ms 25492 KB Output is correct
7 Correct 192 ms 26028 KB Output is correct
8 Correct 247 ms 23624 KB Output is correct
9 Correct 1215 ms 24652 KB Output is correct
10 Correct 454 ms 22156 KB Output is correct
11 Correct 2292 ms 31260 KB Output is correct
12 Correct 535 ms 26492 KB Output is correct
13 Correct 171 ms 26120 KB Output is correct
14 Correct 1145 ms 30928 KB Output is correct
15 Correct 751 ms 28456 KB Output is correct
16 Correct 1204 ms 30520 KB Output is correct
17 Correct 273 ms 26144 KB Output is correct
18 Correct 1326 ms 30960 KB Output is correct
19 Correct 43 ms 15448 KB Output is correct
20 Correct 134 ms 15248 KB Output is correct
21 Correct 231 ms 15408 KB Output is correct
22 Correct 788 ms 15448 KB Output is correct
23 Correct 754 ms 15600 KB Output is correct
24 Correct 137 ms 14936 KB Output is correct
25 Correct 656 ms 15344 KB Output is correct
26 Correct 702 ms 26640 KB Output is correct
27 Correct 1079 ms 28080 KB Output is correct
28 Correct 1165 ms 28168 KB Output is correct
29 Correct 1034 ms 24332 KB Output is correct
30 Correct 2212 ms 30848 KB Output is correct
31 Correct 2001 ms 31272 KB Output is correct
32 Correct 1988 ms 30608 KB Output is correct