oj.uz

Submission #587653

# Submission time Handle Problem Language Result Execution time Memory
587653 2022-07-02T07:44:38 Z MilosMilutinovic The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 2866 ms 99672 KB 
/**
 *    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 / 0.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9808 KB Output is correct
2 Correct 6 ms 9808 KB Output is correct
3 Correct 6 ms 9808 KB Output is correct
4 Correct 33 ms 11540 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 29320 KB Output is correct
2 Correct 232 ms 29304 KB Output is correct
3 Correct 357 ms 20228 KB Output is correct
4 Correct 1570 ms 62368 KB Output is correct
5 Correct 625 ms 17916 KB Output is correct
6 Correct 2511 ms 95176 KB Output is correct
7 Correct 767 ms 34528 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 29224 KB Output is correct
2 Correct 2040 ms 96820 KB Output is correct
3 Correct 1349 ms 61472 KB Output is correct
4 Correct 2247 ms 94628 KB Output is correct
5 Correct 392 ms 33220 KB Output is correct
6 Correct 2866 ms 94872 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 11164 KB Output is correct
2 Correct 207 ms 10268 KB Output is correct
3 Correct 323 ms 10416 KB Output is correct
4 Correct 928 ms 12308 KB Output is correct
5 Correct 927 ms 12112 KB Output is correct
6 Correct 201 ms 10064 KB Output is correct
7 Correct 839 ms 11328 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 6 ms 9808 KB Output is correct
3 Correct 6 ms 9808 KB Output is correct
4 Correct 6 ms 9808 KB Output is correct
5 Correct 33 ms 11540 KB Output is correct
6 Correct 227 ms 29320 KB Output is correct
7 Correct 232 ms 29304 KB Output is correct
8 Correct 357 ms 20228 KB Output is correct
9 Correct 1570 ms 62368 KB Output is correct
10 Correct 625 ms 17916 KB Output is correct
11 Correct 2511 ms 95176 KB Output is correct
12 Correct 767 ms 34528 KB Output is correct
13 Correct 198 ms 29224 KB Output is correct
14 Correct 2040 ms 96820 KB Output is correct
15 Correct 1349 ms 61472 KB Output is correct
16 Correct 2247 ms 94628 KB Output is correct
17 Correct 392 ms 33220 KB Output is correct
18 Correct 2866 ms 94872 KB Output is correct
19 Correct 51 ms 11164 KB Output is correct
20 Correct 207 ms 10268 KB Output is correct
21 Correct 323 ms 10416 KB Output is correct
22 Correct 928 ms 12308 KB Output is correct
23 Correct 927 ms 12112 KB Output is correct
24 Correct 201 ms 10064 KB Output is correct
25 Correct 839 ms 11328 KB Output is correct
26 Correct 964 ms 45256 KB Output is correct
27 Correct 1528 ms 61584 KB Output is correct
28 Correct 1552 ms 56636 KB Output is correct
29 Correct 1524 ms 62532 KB Output is correct
30 Correct 2663 ms 95072 KB Output is correct
31 Correct 2264 ms 99672 KB Output is correct
32 Correct 2338 ms 95040 KB Output is correct