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

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];
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);
      |       ^~~~~~~~

Subtask #1
0 / 5.0

#	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	-

Subtask #2
0 / 7.0

#	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	-

Subtask #3
10.0 / 10.0

#	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