Submission #976497

#	Time	Username	Problem	Language	Result	Execution time	Memory
976497		efedmrlr	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2055 ms	23356 KiB

potion

// #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 (stderr)

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
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30