oj.uz

Submission #265211

# Submission time Handle Problem Language Result Execution time Memory
265211 2020-08-14T14:00:38 Z extraterrestrial New Home (APIO18_new_home) C++14
10 / 100
 4699 ms 184204 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), 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--;
        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 22 ms 35584 KB Output is correct
3 Correct 22 ms 35584 KB Output is correct
4 Incorrect 22 ms 35584 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 22 ms 35584 KB Output is correct
3 Correct 22 ms 35584 KB Output is correct
4 Incorrect 22 ms 35584 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 4173 ms 100044 KB Output is correct
2 Correct 4699 ms 98808 KB Output is correct
3 Correct 3871 ms 100020 KB Output is correct
4 Correct 4289 ms 100096 KB Output is correct
5 Correct 4535 ms 98364 KB Output is correct
6 Correct 4627 ms 98880 KB Output is correct
7 Correct 3850 ms 99980 KB Output is correct
8 Correct 3976 ms 100084 KB Output is correct
9 Correct 4081 ms 100236 KB Output is correct
10 Correct 3954 ms 99496 KB Output is correct
11 Correct 3525 ms 98432 KB Output is correct
12 Correct 3849 ms 99292 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 4038 ms 184204 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 22 ms 35584 KB Output is correct
3 Correct 22 ms 35584 KB Output is correct
4 Incorrect 22 ms 35584 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 22 ms 35584 KB Output is correct
3 Correct 22 ms 35584 KB Output is correct
4 Incorrect 22 ms 35584 KB Output isn't correct
5 Halted 0 ms 0 KB -