oj.uz

Submission #976497

# Submission time Handle Problem Language Result Execution time Memory
976497 2024-05-06T15:42:34 Z efedmrlr The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2055 ms 23356 KB 
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,popcnt")
#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define MP make_pair

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e5 + 5;
const int MXU = 2e5 + 5;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int C = 50;
int n, d;
array<vector<array<int, 2> >, N> upd;
array<vector<vector<int> >, N> lst; 
array<int, N> h;
void init(int N, int D, int H[]) {
    n = N, d = D;
    REP(i, n) h[i] = H[i]; 
}

void make_upd(vector<int> &vec, vector<int> &us) {
    
    sort(all(us));
    vector<int> tmp;
    int i = 0, j = 0;

    auto push = [&tmp](int x) {
        if(tmp.size() && tmp.back() == x) tmp.pop_back();
        else tmp.pb(x);
    };

    while(i < vec.size() || j < us.size()) {
        if(i >= vec.size()) {
            push(us[j]);
            j++;
        }
        else if(j >= us.size()) {
            push(vec[i]);
            i++;
        }
        else if(vec[i] < us[j]) {
            push(vec[i]);
            i++;
        }
        else {
            push(us[j]);
            j++;
        }
    }
    swap(tmp, vec);

} 

void upd_int(vector<int> &vec, int node, int v) {
    int r = (int)(upper_bound(all(upd[node]), array<int,2>({v, INF})) - upd[node].begin());
    if(r == 0) {
        vec = vector<int>();
        return;
    }
    r--;
    r /= C;
    vec = lst[node][r];
    r *= C;
    int ind = r;
    vector<int> us;
    for(; ind < upd[node].size() && upd[node][ind][0] <= v; ind++) {
        us.pb(upd[node][ind][1]);
    }
    make_upd(vec, us);
}

void curseChanges(int U, int A[], int B[]) {
    REP(i, U) {
        upd[A[i]].pb({i + 1, B[i]});
        upd[B[i]].pb({i + 1, A[i]});
    }
    for(int node = 0; node < N; node++) {
        lst[node].pb(vector<int>());
        int last = 0;
        for(int j = C; j < upd[node].size(); j += C) {
            vector<int> us;
            for(int i = last; i < j; i++) {
                us.pb(upd[node][i][1]);
            }
            lst[node].pb(lst[node].back());
            make_upd(lst[node][(int)lst[node].size() - 1], us);
            last = j;
        }
    }
}
auto comp = [](int x, int y) {
    return h[x] < h[y];
};
int question(int x, int y, int v) {
    vector<int> lstx, lsty;
    upd_int(lstx, x, v);
    upd_int(lsty, y, v);
    sort(all(lstx), comp);
    sort(all(lsty), comp);
    int ret = INF;
    int i = 0, j = 0;
    // cout << "lstx: ";
    // for(auto c: lstx) {
    //     cout << c << " ";
    // }
    // cout << "\n";
    // cout << "lsty: ";
    // for(auto c: lsty) {
    //     cout << c << " ";
    // }
    // cout << "\n";
    while(i < lstx.size() && j < lsty.size()) {
        ret = min(ret, abs(h[lstx[i]] - h[lsty[j]]) );
        if(h[lstx[i]] < h[lsty[j]]) {
            i++;
        }
        else {
            j++;
        }
    }
    return ret;
}

Compilation message

potion.cpp: In function 'void make_upd(std::vector<int>&, std::vector<int>&)':
potion.cpp:45:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while(i < vec.size() || j < us.size()) {
      |           ~~^~~~~~~~~~~~
potion.cpp:45:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while(i < vec.size() || j < us.size()) {
      |                             ~~^~~~~~~~~~~
potion.cpp:46:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         if(i >= vec.size()) {
      |            ~~^~~~~~~~~~~~~
potion.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         else if(j >= us.size()) {
      |                 ~~^~~~~~~~~~~~
potion.cpp: In function 'void upd_int(std::vector<int>&, int, int)':
potion.cpp:79:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(; ind < upd[node].size() && upd[node][ind][0] <= v; ind++) {
      |           ~~~~^~~~~~~~~~~~~~~~~~
potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int j = C; j < upd[node].size(); j += C) {
      |                        ~~^~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:125:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     while(i < lstx.size() && j < lsty.size()) {
      |           ~~^~~~~~~~~~~~~
potion.cpp:125:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     while(i < lstx.size() && j < lsty.size()) {
      |                              ~~^~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8368 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8536 KB Output is correct
2 Correct 7 ms 8536 KB Output is correct
3 Correct 7 ms 8384 KB Output is correct
4 Correct 16 ms 9684 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 16732 KB Output is correct
2 Correct 124 ms 16236 KB Output is correct
3 Correct 182 ms 14696 KB Output is correct
4 Correct 1035 ms 20192 KB Output is correct
5 Correct 315 ms 15160 KB Output is correct
6 Correct 2055 ms 23244 KB Output is correct
7 Correct 392 ms 17312 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 16768 KB Output is correct
2 Correct 705 ms 22448 KB Output is correct
3 Correct 475 ms 19540 KB Output is correct
4 Correct 725 ms 22660 KB Output is correct
5 Correct 181 ms 16800 KB Output is correct
6 Correct 808 ms 22480 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8792 KB Output is correct
2 Correct 108 ms 8976 KB Output is correct
3 Correct 165 ms 8792 KB Output is correct
4 Correct 662 ms 9048 KB Output is correct
5 Correct 641 ms 9144 KB Output is correct
6 Correct 108 ms 8792 KB Output is correct
7 Correct 526 ms 8880 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8368 KB Output is correct
2 Correct 7 ms 8536 KB Output is correct
3 Correct 7 ms 8536 KB Output is correct
4 Correct 7 ms 8384 KB Output is correct
5 Correct 16 ms 9684 KB Output is correct
6 Correct 128 ms 16732 KB Output is correct
7 Correct 124 ms 16236 KB Output is correct
8 Correct 182 ms 14696 KB Output is correct
9 Correct 1035 ms 20192 KB Output is correct
10 Correct 315 ms 15160 KB Output is correct
11 Correct 2055 ms 23244 KB Output is correct
12 Correct 392 ms 17312 KB Output is correct
13 Correct 116 ms 16768 KB Output is correct
14 Correct 705 ms 22448 KB Output is correct
15 Correct 475 ms 19540 KB Output is correct
16 Correct 725 ms 22660 KB Output is correct
17 Correct 181 ms 16800 KB Output is correct
18 Correct 808 ms 22480 KB Output is correct
19 Correct 37 ms 8792 KB Output is correct
20 Correct 108 ms 8976 KB Output is correct
21 Correct 165 ms 8792 KB Output is correct
22 Correct 662 ms 9048 KB Output is correct
23 Correct 641 ms 9144 KB Output is correct
24 Correct 108 ms 8792 KB Output is correct
25 Correct 526 ms 8880 KB Output is correct
26 Correct 557 ms 18480 KB Output is correct
27 Correct 891 ms 19972 KB Output is correct
28 Correct 1010 ms 19672 KB Output is correct
29 Correct 879 ms 20216 KB Output is correct
30 Correct 1965 ms 23356 KB Output is correct
31 Correct 1757 ms 22224 KB Output is correct
32 Correct 1748 ms 22876 KB Output is correct