oj.uz

Submission #265225

# Submission time Handle Problem Language Result Execution time Memory
265225 2020-08-14T14:07:43 Z extraterrestrial New Home (APIO18_new_home) C++14
10 / 100
 4452 ms 184376 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back  
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll    
 
const int N = 3e5 + 10;
vector<pair<int, int>> add[N], del[N], que[N];
multiset<int> flex[N];
int ans[N];
 
const int M = 5e6 + 10;
int mn[M], mx[M];
void build_min(int v, int l, int r) {
  mn[v] = 1e9;
  if (l == r) {
    return;
  }
  int mid = (l + r) / 2;
  build_min(2 * v, l, mid);
  build_min(2 * v + 1, mid + 1, r);
}
 
void build_max(int v, int l, int r) {
  mx[v] = 0;
  if (l == r) {
    return;
  }
  int mid = (l + r) / 2;
  build_max(2 * v, l, mid);
  build_max(2 * v + 1, mid + 1, r);
}
 
void update_min(int v, int l, int r, int a, int b, int vl) {
  if (l > b || r < a) {
    return;
  }
  if (l >= a && r <= b) {
    mn[v] = min(mn[v], vl);
    return;
  }
  int mid = (l + r) / 2;
  update_min(2 * v, l, mid, a, b, vl);
  update_min(2 * v + 1, mid + 1, r, a, b, vl);
}
 
void update_max(int v, int l, int r, int a, int b, int vl) {
  if (l > b || r < a) {
    return;
  }
  if (l >= a && r <= b) {
    mx[v] = max(mx[v], vl);
    return;
  }
  int mid = (l + r) / 2;
  update_max(2 * v, l, mid, a, b, vl);
  update_max(2 * v + 1, mid + 1, r, a, b, vl); 
}
 
int get_min(int v, int l, int r, int need) {
  if (l == r) {
    return mn[v];
  }
  int mid = (l + r) / 2;
  if (need <= mid) {
    return min(mn[v], get_min(2 * v, l, mid, need));
  }
  return min(mn[v], get_min(2 * v + 1, mid + 1, r, need));
}
 
int get_max(int v, int l, int r, int need) {
  if (l == r) {
    return mx[v];
  }
  int mid = (l + r) / 2;
  if (need <= mid) {
    return max(mx[v], get_max(2 * v, l, mid, need));
  }
  return max(mx[v], get_max(2 * v + 1, mid + 1, r, need));
}
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); 
  cout.tie(0);
  int n, k, q;
  cin >> n >> k >> q;
  vector<int> x(n), type(n), l(n), r(n), interesting, coord;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> type[i] >> l[i] >> r[i];
    interesting.pb(l[i]);
    interesting.pb(r[i]);
    coord.pb(x[i]);
    type[i]--;
  }
  vector<int> pos(q), tt(q);
  for (int i = 0; i < q; i++) {
    cin >> pos[i] >> tt[i];
    interesting.pb(tt[i]);
    coord.pb(pos[i]);
  }
 
  sort(all(coord));
  coord.resize(unique(all(coord)) - coord.begin());
  for (int &x : coord) {
    cerr << x << ' ';
  }
  cerr << '\n';
  build_min(1, 1, SZ(coord));
  build_max(1, 1, SZ(coord));
  for (int i = 0; i < n; i++) {
    x[i] = upper_bound(all(coord), x[i]) - coord.begin();
    flex[type[i]].insert(x[i]);
  }
  for (int i = 0; i < q; i++) {
    pos[i] = upper_bound(all(coord), pos[i]) - coord.begin();
  }
 
  sort(all(interesting));
  interesting.resize(unique(all(interesting)) - interesting.begin());
  for (int i = 0; i < n; i++) {
    l[i] = upper_bound(all(interesting), l[i]) - interesting.begin();
    r[i] = upper_bound(all(interesting), r[i]) - interesting.begin();
  }
  for (int i = 0; i < q; i++) {
    tt[i] = upper_bound(all(interesting), tt[i]) - interesting.begin();
  }
  int max_time = SZ(interesting);
  bool have_empty = false;
  for (int cur_type = 0; cur_type < k; cur_type++) {
    if (flex[cur_type].empty()) {
      have_empty = true;
      break;
    }
    update_max(1, 1, SZ(coord), 1, *flex[cur_type].begin(), *flex[cur_type].begin());
    update_min(1, 1, SZ(coord), *flex[cur_type].rbegin(), SZ(coord), *flex[cur_type].rbegin());
    auto it = flex[cur_type].begin();
    for(;;) {
      auto it2 = it;
      it2++;
      if (it2 == flex[cur_type].end()) {
        break;
      }
      int l = *it, r = *it2;
      while (r - l > 1) {
        int mid = (l + r) / 2;
        if (coord[mid - 1] - coord[*it - 1] <= coord[*it2 - 1] - coord[mid - 1]) {
          l = mid;
        }
        else {
          r = mid;
        }
      }
      update_min(1, 1, SZ(coord), *it, l, *it);
      update_max(1, 1, SZ(coord), r, *it2, *it2);
      it++;
    }
  }
  for (int i = 0; i < n; i++) {
    //add[l[i]].pb({x[i], type[i]});
    del[r[i]].pb({x[i], type[i]});
  }
  for (int i = 0; i < q; i++) {
    que[tt[i]].pb({pos[i], i});
  }
  for (int cur_time = 1; cur_time <= max_time; cur_time++) {
    /*for (auto it : add[cur_time]) {
      have[it.S].insert(it.F);
    }*/
    for (auto it : que[cur_time]) {
      if (have_empty) {
        ans[it.S] = 1e9;
        continue;
      }
      int lpos = get_min(1, 1, SZ(coord), it.F), rpos = get_max(1, 1, SZ(coord), it.F);
      if (lpos <= it.F) {
        ans[it.S] = max(ans[it.S], coord[it.F - 1] - coord[lpos - 1]);
      }
      if (rpos >= it.F) {
        ans[it.S] = max(ans[it.S], coord[rpos - 1] - coord[it.F - 1]);
      } 
    }
    for (auto cpar : del[cur_time]) {
      if (have_empty) {
        break;
      }
      flex[cpar.S].erase(flex[cpar.S].find(cpar.F));
      if (flex[cpar.S].find(cpar.F) != flex[cpar.S].end()) {
        continue;
      }
      if (flex[cpar.S].empty()) {
        have_empty = true;
        break;
      }
      auto it2 = flex[cpar.S].upper_bound(cpar.F);
      if (it2 == flex[cpar.S].end()) {
        update_min(1, 1, SZ(coord), *flex[cpar.S].rbegin(), SZ(coord), *flex[cpar.S].rbegin());
      } 
      else if (it2 == flex[cpar.S].begin()) {
        update_max(1, 1, SZ(coord), 1, *flex[cpar.S].begin(), *flex[cpar.S].begin());
      } 
      else {
        auto it = it2;
        it--;
        if (*it >= cpar.F || *it2 <= cpar.F) {
          exit(0);
        }
        int l = *it, r = *it2;
        while (r - l > 1) {
          int mid = (l + r) / 2;
          if (coord[mid - 1] - coord[*it - 1] <= coord[*it2 - 1] - coord[mid - 1]) {
            l = mid;
          }
          else {
            r = mid;
          }
        }
        update_min(1, 1, SZ(coord), *it, l, *it);
        update_max(1, 1, SZ(coord), l + 1, *it2, *it2);   
      }    
    }
  }
  for (int i = 0; i < q; i++) {
    if (ans[i] == 1e9) {
      cout << -1 << '\n';
    }
    else {
      cout << ans[i] << '\n';
    }
  }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35584 KB Output is correct
2 Correct 23 ms 35584 KB Output is correct
3 Correct 25 ms 35584 KB Output is correct
4 Incorrect 23 ms 35576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35584 KB Output is correct
2 Correct 23 ms 35584 KB Output is correct
3 Correct 25 ms 35584 KB Output is correct
4 Incorrect 23 ms 35576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4102 ms 100144 KB Output is correct
2 Correct 4452 ms 98944 KB Output is correct
3 Correct 3731 ms 100332 KB Output is correct
4 Correct 4223 ms 100168 KB Output is correct
5 Correct 4439 ms 98328 KB Output is correct
6 Correct 4415 ms 98768 KB Output is correct
7 Correct 3584 ms 100056 KB Output is correct
8 Correct 3861 ms 100372 KB Output is correct
9 Correct 3864 ms 100240 KB Output is correct
10 Correct 3785 ms 99472 KB Output is correct
11 Correct 3586 ms 98652 KB Output is correct
12 Correct 3903 ms 99352 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35584 KB Output is correct
2 Correct 23 ms 35584 KB Output is correct
3 Correct 25 ms 35584 KB Output is correct
4 Incorrect 23 ms 35576 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35584 KB Output is correct
2 Correct 23 ms 35584 KB Output is correct
3 Correct 25 ms 35584 KB Output is correct
4 Incorrect 23 ms 35576 KB Output isn't correct
5 Halted 0 ms 0 KB -