oj.uz

Submission #607474

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

const int N = 100000;

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() == d) {
      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() == d) {
      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 4 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 5 ms 5092 KB Output is correct
4 Correct 17 ms 5912 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 21344 KB Output is correct
2 Correct 311 ms 21352 KB Output is correct
3 Correct 245 ms 12484 KB Output is correct
4 Correct 781 ms 13340 KB Output is correct
5 Correct 168 ms 15608 KB Output is correct
6 Correct 1043 ms 39908 KB Output is correct
7 Correct 402 ms 20068 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 21256 KB Output is correct
2 Correct 1586 ms 21320 KB Output is correct
3 Correct 566 ms 20636 KB Output is correct
4 Correct 806 ms 40260 KB Output is correct
5 Correct 272 ms 21132 KB Output is correct
6 Correct 923 ms 39848 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6096 KB Output is correct
2 Correct 71 ms 5580 KB Output is correct
3 Correct 186 ms 5456 KB Output is correct
4 Correct 439 ms 5956 KB Output is correct
5 Correct 344 ms 6096 KB Output is correct
6 Correct 66 ms 5588 KB Output is correct
7 Correct 475 ms 5544 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5 ms 5092 KB Output is correct
5 Correct 17 ms 5912 KB Output is correct
6 Correct 272 ms 21344 KB Output is correct
7 Correct 311 ms 21352 KB Output is correct
8 Correct 245 ms 12484 KB Output is correct
9 Correct 781 ms 13340 KB Output is correct
10 Correct 168 ms 15608 KB Output is correct
11 Correct 1043 ms 39908 KB Output is correct
12 Correct 402 ms 20068 KB Output is correct
13 Correct 254 ms 21256 KB Output is correct
14 Correct 1586 ms 21320 KB Output is correct
15 Correct 566 ms 20636 KB Output is correct
16 Correct 806 ms 40260 KB Output is correct
17 Correct 272 ms 21132 KB Output is correct
18 Correct 923 ms 39848 KB Output is correct
19 Correct 38 ms 6096 KB Output is correct
20 Correct 71 ms 5580 KB Output is correct
21 Correct 186 ms 5456 KB Output is correct
22 Correct 439 ms 5956 KB Output is correct
23 Correct 344 ms 6096 KB Output is correct
24 Correct 66 ms 5588 KB Output is correct
25 Correct 475 ms 5544 KB Output is correct
26 Correct 497 ms 16900 KB Output is correct
27 Correct 672 ms 20636 KB Output is correct
28 Correct 590 ms 22664 KB Output is correct
29 Correct 602 ms 13332 KB Output is correct
30 Correct 981 ms 40512 KB Output is correct
31 Correct 2186 ms 18756 KB Output is correct
32 Correct 882 ms 39388 KB Output is correct