Submission #587653

#	Time	Username	Problem	Language	Result	Execution time	Memory
587653		MilosMilutinovic	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	2866 ms	99672 KiB

potion

/**
 *    author:  wxhtzdy
 *    created: 01.07.2022 22:14:54
**/
#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}
string to_string(const char* s) {
  return to_string((string) s);
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int MAX = 200005;
const int MAGIC = 50;
               
int a[MAX], p[MAX], q[MAX];
int order[MAX], id[MAX];        
vector<int> qs[MAX];
vector<set<int>> my[MAX];

void init(int n, int d, int h[]) {
  for (int i = 0; i < n; i++) {
    a[i] = h[i];
    order[i] = i;
  }             
  sort(order, order + n, [&](int i, int j) {
    return a[i] < a[j];
  });
  sort(a, a + n);
  for (int i = 0; i < n; i++) {
    id[order[i]] = i;
  }
}

void curseChanges(int u, int a[], int b[]) {
  for (int i = 0; i < u; i++) {
    a[i] = id[a[i]];
    b[i] = id[b[i]];
    qs[a[i]].push_back(i);
    qs[b[i]].push_back(i);
    p[i] = a[i];
    q[i] = b[i];
  }                   
  for (int i = 0; i < MAX; i++) {
    if (qs[i].empty()) {
      continue;
    }
    set<int> st;                      
    for (int j = 0; j < (int) qs[i].size(); j++) {
      int he = (i ^ p[qs[i][j]] ^ q[qs[i][j]]);
      if (st.find(he) != st.end()) {
        st.erase(st.find(he));
      } else {
        st.insert(he);
      }
      if (j % MAGIC == 0) {
        my[i].push_back(st);
      }
    }
  }
}

int question(int x, int y, int v) {
  --v;
  x = id[x];
  y = id[y];
  vector<int> xs;
  vector<int> ys;                     
  {
    int i = lower_bound(qs[x].begin(), qs[x].end(), v + 1) - qs[x].begin();
    --i;           
    if (i >= 0) {
      set<int> st = my[x][i / MAGIC];
      for (int j = (i / MAGIC) * MAGIC + 1; j <= i; j++) {
        int he = (x ^ p[qs[x][j]] ^ q[qs[x][j]]);
        if (st.find(he) != st.end()) {
          st.erase(st.find(he));
        } else {
          st.insert(he);
        }
      }
      for (int j : st) {
        xs.push_back(a[j]);
      }
    }
  }
  {
    int i = lower_bound(qs[y].begin(), qs[y].end(), v + 1) - qs[y].begin();
    --i;     
    if (i >= 0) {
      set<int> st = my[y][i / MAGIC];
      for (int j = (i / MAGIC) * MAGIC + 1; j <= i; j++) {
        int he = (y ^ p[qs[y][j]] ^ q[qs[y][j]]);
        if (st.find(he) != st.end()) {
          st.erase(st.find(he));
        } else {
          st.insert(he);
        }
      }
      for (int j : st) {
        ys.push_back(a[j]);
      }
    }
  }
  assert((int) xs.size() <= 500);
  assert((int) ys.size() <= 500);
  int ptr = 0;
  int ans = 1e9;
  for (int i = 0; i < (int) xs.size(); i++) {
    while (ptr + 1 < (int) ys.size() && xs[i] > ys[ptr]) {
      ptr += 1;
    }   
    if (ptr < (int) ys.size()) {
      ans = min(ans, abs(xs[i] - ys[ptr]));
    }
    if (ptr > 0) {
      ans = min(ans, abs(xs[i] - ys[ptr - 1]));
    }
  }
  return ans;  
}

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30