oj.uz

Submission #607481

# Submission time Handle Problem Language Result Execution time Memory
607481 2022-07-26T18:13:15 Z lunchbox The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2223 ms 29392 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100000, B = 300;

int n, d, u, q, h[N];
vector<vector<tuple<int, int, int>>> ev[N];
vector<int> tt[N];

void init(int n_, int d_, int h_[]) {
  n = n_, d = d_;
  for (int i = 0; i < n; i++)
    h[i] = h_[i];
}
void curseChanges(int u_, int i_[], int j_[]) {
  u = u_;
  for (int k = 1; k <= u; k++) {
    int i = i_[k - 1], j = j_[k - 1];
    if (ev[i].size() == 0 || (int) ev[i].back().size() == B) {
      if (ev[i].size() == 0)
        ev[i].push_back({});
      else  {
        sort(ev[i].back().begin(), ev[i].back().end());
        vector<pair<int, int>> v;
        for (auto [w, x, t] : ev[i].back())
          if (v.size() == 0 || v.back() != make_pair(w, x))
            v.push_back({w, x});
          else
            v.pop_back();
        ev[i].push_back({});
        for (auto [w, x] : v)
          ev[i].back().push_back(make_tuple(w, x, k - 1));
      }
      tt[i].push_back(k);
    }
    ev[i].back().push_back({h[j], j, k});
    if (ev[j].size() == 0 || (int) ev[j].back().size() == B) {
      if (ev[j].size() == 0)
        ev[j].push_back({});
      else {
        sort(ev[j].back().begin(), ev[j].back().end());
        vector<pair<int, int>> v;
        for (auto [w, x, t] : ev[j].back())
          if (v.size() == 0 || v.back() != make_pair(w, x))
            v.push_back({w, x});
          else
            v.pop_back();
        ev[j].push_back({});
        for (auto [w, x] : v)
          ev[j].back().push_back(make_tuple(w, x, k - 1));
      }
      tt[j].push_back(k);
    }
    ev[j].back().push_back({h[i], i, k});
  }
  for (int i = 0; i < n; i++)
    if (ev[i].size())
      sort(ev[i].back().begin(), ev[i].back().end());
}
int question(int i, int j, int k) {
  int p;
  if (tt[i].size() == 0 || tt[j].size() == 0 || tt[i][0] > k || tt[j][0] > k)
    return 1000000000;
  p = upper_bound(tt[i].begin(), tt[i].end(), k) - tt[i].begin() - 1;
  vector<pair<int, int>> wi;
  for (auto [w, x, t] : ev[i][p]) {
    if (t > k)
      continue;
    if (wi.size() == 0 || wi.back() != make_pair(w, x))
      wi.push_back({w, x});
    else
      wi.pop_back();
  }
  p = upper_bound(tt[j].begin(), tt[j].end(), k) - tt[j].begin() - 1;
  vector<pair<int, int>> wj;
  for (auto [w, x, t] : ev[j][p]) {
    if (t > k)
      continue;
    if (wj.size() == 0 || wj.back() != make_pair(w, x))
      wj.push_back({w, x});
    else
      wj.pop_back();
  }
  int ans = 1000000000;
  for (int l = 0, r = 0; l < (int) wi.size(); l++) {
    while (r < (int) wj.size() && wi[l].first > wj[r].first)
      ans = min(ans, wi[l].first - wj[r++].first);
    if (r < (int) wj.size())
      ans = min(ans, wj[r].first - wi[l].first);
  }
  return ans;
}

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 3 ms 5072 KB Output is correct
2 Correct 4 ms 5072 KB Output is correct
3 Correct 3 ms 5072 KB Output is correct
4 Correct 17 ms 5996 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 21232 KB Output is correct
2 Correct 214 ms 21288 KB Output is correct
3 Correct 253 ms 15708 KB Output is correct
4 Correct 513 ms 19308 KB Output is correct
5 Correct 170 ms 15800 KB Output is correct
6 Correct 1767 ms 24476 KB Output is correct
7 Correct 407 ms 20016 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 21328 KB Output is correct
2 Correct 1730 ms 17364 KB Output is correct
3 Correct 470 ms 29252 KB Output is correct
4 Correct 1155 ms 24388 KB Output is correct
5 Correct 237 ms 22612 KB Output is correct
6 Correct 1421 ms 24428 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 6096 KB Output is correct
2 Correct 68 ms 5572 KB Output is correct
3 Correct 151 ms 5584 KB Output is correct
4 Correct 310 ms 6100 KB Output is correct
5 Correct 260 ms 6480 KB Output is correct
6 Correct 61 ms 5584 KB Output is correct
7 Correct 328 ms 5696 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 3 ms 5072 KB Output is correct
3 Correct 4 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 17 ms 5996 KB Output is correct
6 Correct 214 ms 21232 KB Output is correct
7 Correct 214 ms 21288 KB Output is correct
8 Correct 253 ms 15708 KB Output is correct
9 Correct 513 ms 19308 KB Output is correct
10 Correct 170 ms 15800 KB Output is correct
11 Correct 1767 ms 24476 KB Output is correct
12 Correct 407 ms 20016 KB Output is correct
13 Correct 201 ms 21328 KB Output is correct
14 Correct 1730 ms 17364 KB Output is correct
15 Correct 470 ms 29252 KB Output is correct
16 Correct 1155 ms 24388 KB Output is correct
17 Correct 237 ms 22612 KB Output is correct
18 Correct 1421 ms 24428 KB Output is correct
19 Correct 40 ms 6096 KB Output is correct
20 Correct 68 ms 5572 KB Output is correct
21 Correct 151 ms 5584 KB Output is correct
22 Correct 310 ms 6100 KB Output is correct
23 Correct 260 ms 6480 KB Output is correct
24 Correct 61 ms 5584 KB Output is correct
25 Correct 328 ms 5696 KB Output is correct
26 Correct 411 ms 21892 KB Output is correct
27 Correct 550 ms 29392 KB Output is correct
28 Correct 623 ms 25508 KB Output is correct
29 Correct 466 ms 19440 KB Output is correct
30 Correct 1479 ms 24232 KB Output is correct
31 Correct 2223 ms 16788 KB Output is correct
32 Correct 1217 ms 24440 KB Output is correct