Submission #237231

#	Time	Username	Problem	Language	Result	Execution time	Memory
237231		rama_pang	New Home (APIO18_new_home)	C++14	100 / 100	2309 ms	94748 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e8;
const int MAXN = 3e5 + 5;

int N, K, Q;
int X[MAXN];
int ans[MAXN];

vector<array<int, 2>> shops[MAXN]; // shops[type] = (time, id)
array<int, 3> queries[MAXN]; // (x-coord, time, id)

auto active_cmp = [&](int a, int b) {
  if (X[a] != X[b]) return X[a] < X[b];
  return a < b;
};
map<int, int, decltype(active_cmp)> active(active_cmp);

void Solve() {
  vector<array<int, 4>> lines; // (x1, x2, t1, t2)
  int sz = 2 * N + 1;
  vector<int> segtree(2 * sz, 0); // of time

  for (int k = 0; k < K; k++) {
    active.clear();
    active[N + 0] = 0;
    active[N + 1] = 0;
    for (auto s : shops[k]) {
      if (active.count(s[1]) == 0) {
        auto it1 = active.upper_bound(s[1]);
        auto it2 = it1--;
        lines.push_back({(X[it1->first] + X[it2->first] + 1) >> 1, X[it2->first], it2->second, s[0]});
        it2->second = s[0];
        active[s[1]] = s[0];
      } else {
        auto it1 = active.upper_bound(s[1]);
        auto it2 = it1--;
        lines.push_back({(X[it1->first] + X[it2->first] + 1) >> 1, X[it2->first], it2->second, s[0]});
        it2->second = s[0];
        it2 = it1--;
        lines.push_back({(X[it1->first] + X[it2->first] + 1) >> 1, X[it2->first], it2->second, s[0]});
        active.erase(it2);
      }
    }
    lines.push_back({0, 2 * INF, active[N + 1], sz});
  }

  sort(begin(lines), end(lines));
  for (int q = 0, j = 0; q < Q; q++) {
    while (j < lines.size() && lines[j][0] <= queries[q][0]) {
      for (int l = lines[j][2] + sz, r = lines[j][3] + sz; l < r; l /= 2, r /= 2) {
        if (l & 1) {
          segtree[l] = max(segtree[l], lines[j][1]);
          l++;
        }
        if (r & 1) {
          r--;
          segtree[r] = max(segtree[r], lines[j][1]);
        }
      }
      j++;
    }
    for (int i = queries[q][1] + sz; i > 0; i /= 2) {
      ans[queries[q][2]] = max(ans[queries[q][2]], segtree[i] - queries[q][0]);
    }
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> K >> Q;

  vector<int> times = {0};
  for (int i = 0; i < N; i++) {
    int t, a, b;
    cin >> X[i] >> t >> a >> b;
    t--;
    shops[t].push_back({a, i});
    shops[t].push_back({b + 1, i});
    times.push_back(a);
    times.push_back(b + 1);
  }
  X[N + 0] = - 2 * INF;
  X[N + 1] = + 2 * INF;

  sort(begin(times), end(times));
  for (int i = 0; i < K; i++) {
    for (auto &j : shops[i]) {
      j[0] = lower_bound(begin(times), end(times), j[0]) - begin(times);
    }
    sort(begin(shops[i]), end(shops[i]));
  }

  for (int i = 0; i < Q; i++) {
    cin >> queries[i][0] >> queries[i][1];
    queries[i][2] = i;
    queries[i][1] = upper_bound(begin(times), end(times), queries[i][1]) - begin(times) - 1;
  }
  sort(queries, queries + Q);

  Solve();
  for (int i = 0; i < N; i++) {
    X[i] = INF - X[i] + 1;
  }
  for (int i = 0; i < Q; i++) {
    queries[i][0] = INF - queries[i][0] + 1;
  }
  reverse(queries, queries + Q);
  Solve();

  for (int i = 0; i < Q; i++) {
    if (ans[i] >= INF) ans[i] = -1;
    cout << ans[i] << "\n";
  }
  return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'void Solve()':
new_home.cpp:51:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (j < lines.size() && lines[j][0] <= queries[q][0]) {
            ~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20