Submission #265237

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
265237	2020-08-14T14:15:19 Z	extraterrestrial	New Home (APIO18_new_home)	C++14	10 / 100	4132 ms	184292 KB

new_home

#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;
      }
      if (it.F < 1 || it.F > SZ(coord)) {
        exit(0);
      }
      int lpos = get_min(1, 1, SZ(coord), it.F), rpos = get_max(1, 1, SZ(coord), it.F);
      if (lpos <= it.F) {
        if (lpos < 1 || lpos > SZ(coord)) {
          exit(0);
        }
        ans[it.S] = max(ans[it.S], coord[it.F - 1] - coord[lpos - 1]);
      }
      if (rpos >= it.F) {
        if (rpos < 1 || rpos > SZ(coord)) {
          exit(0);
        }
        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	23 ms	35584 KB	Output is correct
2	Incorrect	22 ms	35584 KB	Output isn't correct
3	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	Incorrect	22 ms	35584 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4132 ms	100052 KB	Output is correct
2	Correct	3725 ms	98888 KB	Output is correct
3	Correct	3741 ms	100188 KB	Output is correct
4	Correct	4008 ms	100020 KB	Output is correct
5	Correct	3772 ms	98400 KB	Output is correct
6	Correct	3766 ms	98792 KB	Output is correct
7	Correct	3578 ms	100068 KB	Output is correct
8	Correct	3795 ms	100048 KB	Output is correct
9	Correct	3908 ms	100092 KB	Output is correct
10	Correct	3995 ms	99412 KB	Output is correct
11	Correct	3391 ms	98584 KB	Output is correct
12	Correct	3498 ms	99440 KB	Output is correct