Submission #66017

#	Time	Username	Problem	Language	Result	Execution time	Memory
66017		funcsr	New Home (APIO18_new_home)	C++17	47 / 100	5040 ms	361368 KiB

new_home

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define MOD 1000000007
#define MAX_N (1<<19)
struct PQ {
  int size = 0;
  priority_queue<int> pq_max, erase_max;
  priority_queue<int, vector<int>, greater<int> > pq_min, erase_min;

  void add(int x) {
    size++;
    pq_min.push(x);
    pq_max.push(x);
  }
  void erase(int x) {
    size--;
    erase_min.push(x);
    erase_max.push(x);
  }
  bool empty() {
    return size==0;
  }
  int min() {
    while (!erase_min.empty() && pq_min.top() == erase_min.top()) pq_min.pop(), erase_min.pop();
    return pq_min.top();
  }
  int max() {
    while (!erase_max.empty() && pq_max.top() == erase_max.top()) pq_max.pop(), erase_max.pop();
    return pq_max.top();
  }
};

inline int dist(PQ &s, int d) {
  if (s.empty()) return 0;
  //else return max(abs(d-*s.begin()), abs(d-*s.rbegin()));
  else return max(d-s.min(), s.max()-d);
}

struct SegTree {
  PQ seg[MAX_N*2-1];
  void add(int a, int b, int x, int k=0, int l=0, int r=MAX_N) {
    if (b <= l || r <= a) return;
    if (a <= l && r <= b) {
      seg[k].add(x);
      return;
    }
    add(a, b, x, k*2+1, l, (l+r)/2);
    add(a, b, x, k*2+2, (l+r)/2, r);
  }
  void remove(int a, int b, int x, int k=0, int l=0, int r=MAX_N) {
    if (b <= l || r <= a) return;
    if (a <= l && r <= b) {
      seg[k].erase(x);
      return;
    }
    remove(a, b, x, k*2+1, l, (l+r)/2);
    remove(a, b, x, k*2+2, (l+r)/2, r);
  }
  int query(int k, int x) {
    k += MAX_N-1;
    int m = dist(seg[k], x);
    while (k > 0) {
      k = (k-1)/2;
      m = max(m, dist(seg[k], x));
    }
    return m;
  }
} seg;

int N, K, Q;
int X[300000], T[300000], A[300000], B[300000];
int L[300000], Y[300000];
#define MAX_Y 300000
vector<int> Gopen[MAX_Y];
vector<int> Gclose[MAX_Y];
vector<int> Gquery[MAX_Y];
int rangeL[300000], rangeR[300000];
int ans[300000];
vector<int> years, xs;

inline void updateRangeL(int id, int l) {
  rangeL[id] = lower_bound(all(xs), l) - xs.begin();
}
inline void updateRangeR(int id, int r) {
  rangeR[id] = upper_bound(all(xs), r) - xs.begin() - 1;
}
inline void addRange(int id) {
  int l = rangeL[id], r = rangeR[id];
  if (rangeL[id] <= r) seg.add(l, r+1, X[id]);
}
inline void removeRange(int id) {
  int l = rangeL[id], r = rangeR[id];
  if (l <= r) seg.remove(l, r+1, X[id]);
}

set<P> kind[300000]; // (pos, i)

void add(int k, P val) {
  int x = val._2;
  auto it = kind[k].lower_bound(val);
  int a = -1, b = -1;
  if (it != kind[k].end()) b = it->_2;
  if (it != kind[k].begin()) a = (--it)->_2;
  kind[k].insert(val);

  if (a != -1) removeRange(a);
  if (b != -1) removeRange(b);

  if (a == -1) updateRangeL(x, 0);
  else {
    updateRangeR(a, (X[a]+X[x])/2);
    updateRangeL(x, (X[a]+X[x])/2);
  }
  if (b == -1) updateRangeR(x, 2e8);
  else {
    updateRangeR(x, (X[b]+X[x])/2);
    updateRangeL(b, (X[b]+X[x])/2);
  }

  if (a != -1) addRange(a);
  if (b != -1) addRange(b);
  addRange(x);
}

void remove(int k, P val) {
  int x = val._2;
  kind[k].erase(val);
  auto it = kind[k].lower_bound(val);
  int a = -1, b = -1;
  if (it != kind[k].end()) b = it->_2;
  if (it != kind[k].begin()) a = (--it)->_2;

  if (a != -1) removeRange(a);
  if (b != -1) removeRange(b);
  removeRange(x);

  if (a != -1) updateRangeR(a, (b==-1)?2e8:((X[a]+X[b])/2));
  if (b != -1) updateRangeL(b, (a==-1)?0:((X[a]+X[b])/2));

  if (a != -1) addRange(a);
  if (b != -1) addRange(b);
}

inline int maxDist(int pos) {
  return seg.query(index(xs, pos), pos);
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> K >> Q;
  rep(i, N) {
    cin >> X[i] >> T[i] >> A[i] >> B[i];
    X[i] *= 2;
    T[i]--;
  }
  rep(i, Q) {
    cin >> L[i] >> Y[i];
    L[i] *= 2;
    xs.pb(L[i]);
    years.pb(Y[i]);
  }
  sort(all(years)); uniq(years);
  assert(years.size() <= MAX_Y);
  rep(i, N) Gopen[index(years, A[i])].pb(i);
  rep(i, N) Gclose[index(years, B[i]+1)].pb(i);
  rep(i, Q) Gquery[index(years, Y[i])].pb(i);

  sort(all(xs)); uniq(xs);

  int zero = K;
  rep(y, years.size()) {
    for (int i : Gopen[y]) {
      if (kind[T[i]].empty()) zero--;
      add(T[i], P(X[i], i));
    }
    for (int i : Gclose[y]) {
      remove(T[i], P(X[i], i));
      if (kind[T[i]].empty()) zero++;
    }
    for (int q : Gquery[y]) {
      int m = -1;
      if (zero == 0) m = maxDist(L[q])/2;
      ans[q] = m;
    }
  }
  rep(i, Q) cout << ans[i] << "\n";
  return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:17:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
new_home.cpp:192:3: note: in expansion of macro 'rep'
   rep(y, years.size()) {
   ^~~

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