Submission #264949

# Submission time Handle Problem Language Result Execution time Memory
264949 2020-08-14T11:32:56 Z extraterrestrial New Home (APIO18_new_home) C++14
10 / 100
1288 ms 98168 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];
vector<int> flex[N];
int ans[N];
multiset<int> have[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]].pb(x[i]);
  }
  for (int i = 0; i < q; i++) {
    pos[i] = upper_bound(all(coord), pos[i]) - coord.begin();
  }
  for (int i = 0; i < k; i++) {
    sort(all(flex[i]));
  }

  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][0], flex[cur_type][0]);
    update_min(1, 1, SZ(coord), flex[cur_type].back(), SZ(coord), flex[cur_type].back());
    for (int pos = 0; pos + 1 < SZ(flex[cur_type]); pos++) {
      int l = flex[cur_type][pos], r = flex[cur_type][pos + 1];
      while (r - l > 1) {
        int mid = (l + r) / 2;
        if (coord[mid - 1] - coord[flex[cur_type][pos] - 1] <= coord[flex[cur_type][pos + 1] - 1] - coord[mid - 1]) {
          l = mid;
        }
        else {
          r = mid;
        }
      }
      update_min(1, 1, SZ(coord), flex[cur_type][pos], l, flex[cur_type][pos]);
      update_max(1, 1, SZ(coord), l + 1, flex[cur_type][pos + 1], flex[cur_type][pos + 1]);
    }
  }
  for (int i = 0; i < q; i++) {
    if (have_empty) {
      cout << -1 << '\n';
      continue;
    } 
    int lpos = get_min(1, 1, SZ(coord), pos[i]), rpos = get_max(1, 1, SZ(coord), pos[i]);
    int rez = 0;
    if (lpos <= pos[i]) {
      rez = max(rez, coord[pos[i] - 1] - coord[lpos - 1]);
    }
    if (rpos >= pos[i]) {
      rez = max(rez, coord[rpos - 1] - coord[pos[i] - 1]);
    }
    cout << rez << '\n';
  }
  /*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]) {
      for (int i = 0; i < k; i++) {
        int rez = 1e9;
        auto kek = have[i].upper_bound(it.F);
        if (kek != have[i].end()) {
          rez = min(rez, *kek - it.F);
        }
        if (kek != have[i].begin()) {
          kek--;
          rez = min(rez, it.F - *kek);
        }
        ans[it.S] = max(ans[it.S], rez);
      }
    }
    for (auto it : del[cur_time]) {
      have[it.S].erase(have[it.S].find(it.F));
    }
  }
  for (int i = 0; i < q; i++) {
    if (ans[i] == 1e9) {
      cout << -1 << '\n';
    }
    else {
      cout << ans[i] << '\n';
    }
  }*/
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:138:7: warning: unused variable 'max_time' [-Wunused-variable]
  138 |   int max_time = SZ(interesting);
      |       ^~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 30 ms 42624 KB Output is correct
2 Incorrect 29 ms 42744 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 30 ms 42624 KB Output is correct
2 Incorrect 29 ms 42744 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1288 ms 86760 KB Output is correct
2 Correct 851 ms 89020 KB Output is correct
3 Correct 1020 ms 98168 KB Output is correct
4 Correct 1174 ms 91908 KB Output is correct
5 Correct 881 ms 89828 KB Output is correct
6 Correct 842 ms 88980 KB Output is correct
7 Correct 939 ms 98024 KB Output is correct
8 Correct 1216 ms 91524 KB Output is correct
9 Correct 1144 ms 91396 KB Output is correct
10 Correct 1027 ms 90092 KB Output is correct
11 Correct 681 ms 89080 KB Output is correct
12 Correct 845 ms 90028 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 1244 ms 86760 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 30 ms 42624 KB Output is correct
2 Incorrect 29 ms 42744 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 30 ms 42624 KB Output is correct
2 Incorrect 29 ms 42744 KB Output isn't correct
3 Halted 0 ms 0 KB -