oj.uz

Submission #656518

# Submission time Handle Problem Language Result Execution time Memory
656518 2022-11-07T18:27:15 Z Alex_tz307 The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 964 ms 31536 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int kN = 1e5;
const int INF = 1e9;
const int kBucket = 200;
int N, h[kN], bucketSize[kN];
vector<pair<int, int>> ev[kN];
vector<vector<int>> friends[kN];
bool ap[kN], inVec[kN];
 
void minSelf(int &x, int y) {
  if (y < x) {
    x = y;
  }
}
 
bool fcmp(const int &x, const int &y) {
  if (h[x] != h[y]) {
    return h[x] < h[y];
  }
  return x < y;
}
 
vector<int> findList(const int &x, const int &t) {
  int l = 0, r = (int)ev[x].size() - 1, pos = -1;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (ev[x][mid].first <= t) {
      pos = mid;
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  if (pos == -1) {
    return {};
  }
  int bucket = (pos + 1) / bucketSize[x] - 1;
  vector<int> suff;
  for (int i = (bucket + 1) * bucketSize[x]; i <= pos; ++i) {
    if (!inVec[ev[x][i].second]) {
      suff.emplace_back(ev[x][i].second);
      inVec[ev[x][i].second] = true;
    }
    ap[ev[x][i].second] ^= 1;
  }
  vector<int> realSuff;
  for (const int &y : suff) {
    if (ap[y]) {
      realSuff.emplace_back(y);
    }
    ap[y] = false;
    inVec[y] = false;
  }
  suff = realSuff;
  sort(suff.begin(), suff.end(), fcmp);
  if (bucket < 0) {
    return suff;
  }
  vector<int> sol(friends[x][bucket].size() + suff.size());
  merge(friends[x][bucket].begin(), friends[x][bucket].end(), suff.begin(), suff.end(), sol.begin(), fcmp);
  vector<int> realSol;
  for (int i = 0; i < (int)sol.size(); ++i) {
    int j = i;
    while (j < (int)sol.size() && sol[j] == sol[i]) {
      j += 1;
    }
    if ((j - i) % 2 == 1) {
      realSol.emplace_back(sol[i]);
    }
    i = j - 1;
  }
  return realSol;
}
 
void init(int n, int d, int H[]) {
  N = n;
  for (int i = 0; i < N; ++i) {
    h[i] = H[i];
  }
}
 
void curseChanges(int U, int A[], int B[]) {
  for (int i = 0; i < U; ++i) {
    ev[A[i]].emplace_back(i + 1, B[i]);
    ev[B[i]].emplace_back(i + 1, A[i]);
  }
  vector<int> preff, realFriends;
  for (int x = 0; x < N; ++x) {
    if (ev[x].empty()) {
      continue;
    }
    bucketSize[x] = min((int)sqrt((int)ev[x].size()), kBucket);
    preff.clear();
    for (int i = 0; i < (int)ev[x].size(); ++i) {
      if (!inVec[ev[x][i].second]) {
        preff.emplace_back(ev[x][i].second);
        inVec[ev[x][i].second] = true;
      }
      ap[ev[x][i].second] ^= 1;
      if (i % bucketSize[x] == bucketSize[x] - 1) {
        realFriends.clear();
        for (const int &y : preff) {
          if (ap[y]) {
            realFriends.emplace_back(y);
          } else {
            inVec[y] = false;
          }
        }
        preff = realFriends;
        friends[x].emplace_back(preff);
      }
    }
    if ((int)ev[x].size() % bucketSize[x]) {
      realFriends.clear();
      for (const int &y : preff) {
        if (ap[y]) {
          realFriends.emplace_back(y);
        } else {
          inVec[y] = false;
        }
      }
      preff = realFriends;
      friends[x].emplace_back(preff);
    }
    for (const int &y : preff) {
      ap[y] = false;
      inVec[y] = false;
    }
    for (int i = 0; i < (int)friends[x].size(); ++i) {
      sort(friends[x][i].begin(), friends[x][i].end(), fcmp);
    }
  }
}
 
int question(int x, int y, int v) {
  vector<int> X = findList(x, v);
  if (X.empty()) {
    return INF;
  }
  vector<int> Y = findList(y, v);
  if (Y.empty()) {
    return INF;
  }
  int res = INF, j = 0;
  for (int i = 0; i < (int)X.size(); ++i) {
    while (j < (int)Y.size() && h[Y[j]] <= h[X[i]]) {
      j += 1;
    }
    if (j < (int)Y.size()) {
      minSelf(res, h[Y[j]] - h[X[i]]);
    }
    if (j >= 1) {
      minSelf(res, h[X[i]] - h[Y[j - 1]]);
    }
  }
  return res;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5072 KB Output is correct
2 Correct 4 ms 5072 KB Output is correct
3 Correct 4 ms 5104 KB Output is correct
4 Correct 19 ms 6544 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 30316 KB Output is correct
2 Correct 257 ms 30276 KB Output is correct
3 Correct 231 ms 11564 KB Output is correct
4 Correct 622 ms 22492 KB Output is correct
5 Correct 274 ms 21192 KB Output is correct
6 Correct 964 ms 29240 KB Output is correct
7 Correct 364 ms 25452 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 30340 KB Output is correct
2 Correct 679 ms 21404 KB Output is correct
3 Correct 507 ms 27288 KB Output is correct
4 Correct 695 ms 29080 KB Output is correct
5 Correct 244 ms 30736 KB Output is correct
6 Correct 761 ms 29244 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 6608 KB Output is correct
2 Correct 81 ms 5644 KB Output is correct
3 Correct 167 ms 5584 KB Output is correct
4 Correct 292 ms 6352 KB Output is correct
5 Correct 272 ms 6664 KB Output is correct
6 Correct 80 ms 5840 KB Output is correct
7 Correct 336 ms 5708 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 5 ms 5072 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 4 ms 5104 KB Output is correct
5 Correct 19 ms 6544 KB Output is correct
6 Correct 284 ms 30316 KB Output is correct
7 Correct 257 ms 30276 KB Output is correct
8 Correct 231 ms 11564 KB Output is correct
9 Correct 622 ms 22492 KB Output is correct
10 Correct 274 ms 21192 KB Output is correct
11 Correct 964 ms 29240 KB Output is correct
12 Correct 364 ms 25452 KB Output is correct
13 Correct 230 ms 30340 KB Output is correct
14 Correct 679 ms 21404 KB Output is correct
15 Correct 507 ms 27288 KB Output is correct
16 Correct 695 ms 29080 KB Output is correct
17 Correct 244 ms 30736 KB Output is correct
18 Correct 761 ms 29244 KB Output is correct
19 Correct 51 ms 6608 KB Output is correct
20 Correct 81 ms 5644 KB Output is correct
21 Correct 167 ms 5584 KB Output is correct
22 Correct 292 ms 6352 KB Output is correct
23 Correct 272 ms 6664 KB Output is correct
24 Correct 80 ms 5840 KB Output is correct
25 Correct 336 ms 5708 KB Output is correct
26 Correct 399 ms 20504 KB Output is correct
27 Correct 589 ms 27404 KB Output is correct
28 Correct 576 ms 31536 KB Output is correct
29 Correct 578 ms 22496 KB Output is correct
30 Correct 849 ms 29112 KB Output is correct
31 Correct 887 ms 21020 KB Output is correct
32 Correct 844 ms 29052 KB Output is correct