oj.uz

Submission #265269

# Submission time Handle Problem Language Result Execution time Memory
265269 2020-08-14T14:37:48 Z extraterrestrial New Home (APIO18_new_home) C++14
33 / 100
 4818 ms 119088 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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    

#define FAST_ALLOCATOR_MEMORY 3e8 
#ifdef FAST_ALLOCATOR_MEMORY
int allocator_pos = 0;
char allocator_memory[(int)FAST_ALLOCATOR_MEMORY];
inline void * operator new ( size_t n ) {
  char *res = allocator_memory + allocator_pos;
  allocator_pos += n;
  assert(allocator_pos <= (int)FAST_ALLOCATOR_MEMORY);
  return (void *)res;
}
inline void operator delete ( void * ) noexcept { }
//inline void * operator new [] ( size_t ) { assert(0); }
//inline void operator delete [] ( void * ) { assert(0); }
#endif
 
const int N = 3e5 + 10;
vector<pair<int, int>> del[2 * N], que[2 * 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]) {
      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 26 ms 42624 KB Output is correct
2 Correct 24 ms 42624 KB Output is correct
3 Correct 25 ms 42624 KB Output is correct
4 Incorrect 25 ms 42616 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 42624 KB Output is correct
2 Correct 24 ms 42624 KB Output is correct
3 Correct 25 ms 42624 KB Output is correct
4 Incorrect 25 ms 42616 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 4019 ms 110084 KB Output is correct
2 Correct 4643 ms 108884 KB Output is correct
3 Correct 3700 ms 109984 KB Output is correct
4 Correct 3958 ms 110068 KB Output is correct
5 Correct 4239 ms 108328 KB Output is correct
6 Correct 4400 ms 108652 KB Output is correct
7 Correct 3637 ms 110016 KB Output is correct
8 Correct 3913 ms 110008 KB Output is correct
9 Correct 3951 ms 110032 KB Output is correct
10 Correct 3810 ms 109432 KB Output is correct
11 Correct 3518 ms 108836 KB Output is correct
12 Correct 3727 ms 109396 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4818 ms 105748 KB Output is correct
2 Correct 454 ms 91384 KB Output is correct
3 Correct 4582 ms 117272 KB Output is correct
4 Correct 3748 ms 117676 KB Output is correct
5 Correct 4245 ms 117416 KB Output is correct
6 Correct 4255 ms 117704 KB Output is correct
7 Correct 4358 ms 116560 KB Output is correct
8 Correct 4641 ms 117080 KB Output is correct
9 Correct 3765 ms 119088 KB Output is correct
10 Correct 4165 ms 118956 KB Output is correct
11 Correct 4594 ms 119028 KB Output is correct
12 Correct 4431 ms 118136 KB Output is correct
13 Correct 3538 ms 116096 KB Output is correct
14 Correct 3410 ms 115452 KB Output is correct
15 Correct 3580 ms 116824 KB Output is correct
16 Correct 3918 ms 117960 KB Output is correct
17 Correct 3548 ms 116244 KB Output is correct

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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