oj.uz

Submission #265179

# Submission time Handle Problem Language Result Execution time Memory
265179 2020-08-14T13:40:16 Z extraterrestrial New Home (APIO18_new_home) C++14
10 / 100
 4550 ms 184284 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 (int pos = 0; pos + 1 < SZ(flex[cur_type]); pos++) {
      auto it2 = it;
      it2++;
      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);
      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--;
        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 23 ms 35584 KB Output is correct
2 Correct 24 ms 35636 KB Output is correct
3 Correct 25 ms 35584 KB Output is correct
4 Incorrect 26 ms 35712 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35584 KB Output is correct
2 Correct 24 ms 35636 KB Output is correct
3 Correct 25 ms 35584 KB Output is correct
4 Incorrect 26 ms 35712 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 4220 ms 99984 KB Output is correct
2 Correct 4441 ms 99136 KB Output is correct
3 Correct 3806 ms 103488 KB Output is correct
4 Correct 3980 ms 103180 KB Output is correct
5 Correct 4550 ms 101468 KB Output is correct
6 Correct 4504 ms 102004 KB Output is correct
7 Correct 3809 ms 103252 KB Output is correct
8 Correct 4126 ms 103228 KB Output is correct
9 Correct 4124 ms 103260 KB Output is correct
10 Correct 4150 ms 102592 KB Output is correct
11 Correct 3838 ms 101732 KB Output is correct
12 Correct 3875 ms 102444 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 4081 ms 184284 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 23 ms 35584 KB Output is correct
2 Correct 24 ms 35636 KB Output is correct
3 Correct 25 ms 35584 KB Output is correct
4 Incorrect 26 ms 35712 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

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