oj.uz

Submission #607472

# Submission time Handle Problem Language Result Execution time Memory
607472 2022-07-26T18:09:04 Z lunchbox The Potion of Great Power (CEOI20_potion) C++17
0 / 100
 53 ms 14804 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 ii[], int jj[]) {
  u = u_;
  for (int k = 1; k <= u; k++) {
    int i = ii[k - 1], j = jj[k - 1];
    scanf("%d%d", &i, &j);
    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;
}

Compilation message

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d%d", &i, &j);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 5016 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 4944 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 14804 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 14656 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5 ms 5200 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 5016 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -