Submission #906036

#	Time	Username	Problem	Language	Result	Execution time	Memory
906036		nguyentunglam	New Home (APIO18_new_home)	C++17	100 / 100	4671 ms	378600 KiB

new_home

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 3e5 + 10;

int n, k, q, sz;

int x[N * 3], t[N], a[N], b[N], cost[N], c[N], y[N], ans[N];

int pre[N * 3], nxt[N * 3];

vector<int> rrh, open[N * 3], close[N * 3], event[N * 3];

bool alive[N * 3];

bool bug;

priority_queue<pair<int, int> > bit0[N], bit1[N];

void add0 (int pos, int border, pair<int, int> tmp) {
  while (pos >= border) {
    bit0[pos].push(tmp);
    pos -= pos & -pos;
  }
}

int get0(int pos, int _pos) {
  int ret = 0;
  while (pos <= sz) {
    while (!bit0[pos].empty()) {
      int i = bit0[pos].top().second;
      int j = nxt[i];
      if (alive[i] == 0 || x[i] == x[j] || abs(x[i] - _pos) > abs(x[j] - _pos)) bit0[pos].pop();
      else {
        ret = max(ret, _pos - x[i]);
        break;
      }
    }
    pos += pos & -pos;
  }
  return ret;
}

void add1 (int pos, int border, pair<int, int> tmp) {
  while (pos <= border) {
    bit1[pos].push(tmp);
    pos += pos & -pos;
  }
}

int get1(int pos, int _pos) {
  int ret = 0;
  while (pos) {
    while (!bit1[pos].empty()) {
      int i = bit1[pos].top().second;
      int j = pre[i];
      if (alive[i] == 0 || x[i] == x[j] || abs(x[i] - _pos) > abs(x[j] - _pos)) bit1[pos].pop();
      else {
        ret = max(ret, x[i] - _pos);
        break;
      }
    }
    pos -= pos & -pos;
  }
  return ret;
}

void compress () {
  sort(all(rrh));
  rrh.resize(unique(all(rrh)) - rrh.begin());
}

int id (int x) {
  return upper_bound(all(rrh), x) - rrh.begin();
}

struct BIT {
  vector<pair<int, int> > rrh;
  vector<int> bit;
  int m, lg;
  void compress () {
    sort(all(rrh));
    rrh.resize(unique(all(rrh)) - rrh.begin());
    m = rrh.size();
    lg = log2(m);
    bit.resize(m + 1);
  }

  void up(int pos, int val) {
    while (pos <= m) {
      bit[pos] += val;
      pos += pos & -pos;
    }
  }

  int get (int pos) {
    int ret = 0;
    while (pos) {
      ret += bit[pos];
      pos -= pos & -pos;
    }
    return ret;
  }

  int reach (int sum) {
    int cur = 0, pos = 0;
    for(int j = lg; j >= 0; j--) {
      int x = pos + (1 << j);
      if (x <= m && cur + bit[x] <= sum) cur += bit[pos = x];
    }
    return pos;
  }

  pair<int, int> add (pair<int, int> tmp) {
    int pos = upper_bound(all(rrh), tmp) - rrh.begin();
    up(pos, 1);
    int sum = get(pos);
    int l = reach(sum - 2) + 1;
    int r = reach(sum) + 1;
    l = rrh[l - 1].second;
    r = rrh[r - 1].second;
    return make_pair(l, r);
  }

  pair<int, int> del (pair<int, int> tmp) {
    int pos = upper_bound(all(rrh), tmp) - rrh.begin();
    int sum = get(pos);
    int l = reach(sum - 2) + 1;
    int r = reach(sum) + 1;
    l = rrh[l - 1].second;
    r = rrh[r - 1].second;
    up(pos, -1);
    return make_pair(l, r);
  }
} bit[N];

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n >> k >> q;

  for(int i = 1; i <= n; i++) cin >> x[i] >> t[i] >> a[i] >> b[i];

  for(int i = 1; i <= q; i++) cin >> c[i] >> y[i];

  for(int i = 1; i <= n; i++) {
    rrh.push_back(a[i]);
    rrh.push_back(b[i]);
  }
  for(int i = 1; i <= q; i++) rrh.push_back(y[i]);

  compress();

  for(int i = 1; i <= n; i++) {
    a[i] = id(a[i]);
    b[i] = id(b[i]);
    open[a[i]].push_back(i);
    close[b[i]].push_back(i);
  }

  for(int i = 1; i <= q; i++) {
    y[i] = id(y[i]);
    event[y[i]].push_back(i);
  }

  int m = rrh.size();

  rrh.clear();
  for(int i = 1; i <= q; i++) rrh.push_back(c[i]);
  compress();

  int cnt = n;
  sz = rrh.size();

  for(int i = 1; i <= n; i++) bit[t[i]].rrh.emplace_back(x[i], i);

  for(int i = 1; i <= k; i++) {
    x[cnt + 1] = -1e9;
    x[cnt + 2] = 1e9;
    alive[cnt + 1] = alive[cnt + 2] = 1;
    add1(1, sz, make_pair(x[cnt + 2], cnt + 2));
    nxt[cnt + 1] = cnt + 2;
    pre[cnt + 2] = cnt + 1;

    bit[i].rrh.emplace_back(x[cnt + 1], cnt + 1);
    bit[i].rrh.emplace_back(x[cnt + 2], cnt + 2);

    bit[i].compress();

    bit[i].add(make_pair(x[cnt + 1], cnt + 1));
    bit[i].add(make_pair(x[cnt + 2], cnt + 2));
    cnt += 2;
  }

  for(int cur = 1; cur <= m; cur++) {
    for(int &j : open[cur]) {
      int from, to;
      tie(from, to) = bit[t[j]].add(make_pair(x[j], j));
//      cout << from << " " << to << "add\n";
      int middle;
      middle = id(x[from] + x[j] >> 1);
      int L = id(x[from] - 1) + 1, R = id(x[to]), pos = id(x[j]);

      add0(middle, L, make_pair(-x[from], from));
      add1(middle + 1, pos, make_pair(x[j], j));

      middle = id(x[j] + x[to] >> 1);
      pos = id(x[j] - 1) + 1;

      add0(middle, pos, make_pair(-x[j], j));
      add1(middle + 1, R, make_pair(x[to], to));

      nxt[from] = j;
      pre[j] = from;
      nxt[j] = to;
      pre[to] = j;
      alive[j] = 1;
    }
    for(int &j : event[cur]) {
      int tmp = id(c[j]);
      int cost1 = get0(tmp, c[j]);
      int cost2 = get1(tmp, c[j]);
      ans[j] = max(cost1, cost2);
    }
    for(int &j : close[cur]) {
      int from, to;
      tie(from, to) = bit[t[j]].del(make_pair(x[j], j));

//      cout << bit[1].get(1) << " " << from << " " << to << "del\n";

      int L = id(x[from] - 1) + 1, R = id(x[to]), middle = id(x[from] + x[to] >> 1);
      add0(middle, L, make_pair(-x[from], from));
      add1(middle + 1, R, make_pair(x[to], to));


      nxt[from] = to;
      pre[to] = from;
      alive[j] = 0;
    }
  }

  cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;

  for(int i = 1; i <= q; i++) {
    if (ans[i] > 1e8) ans[i] = -1;
    cout << ans[i] << endl;
  }

}

Compilation message (stderr)

new_home.cpp: In function 'int32_t main()':
new_home.cpp:215:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  215 |       middle = id(x[from] + x[j] >> 1);
      |                   ~~~~~~~~^~~~~~
new_home.cpp:221:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  221 |       middle = id(x[j] + x[to] >> 1);
      |                   ~~~~~^~~~~~~
new_home.cpp:245:71: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  245 |       int L = id(x[from] - 1) + 1, R = id(x[to]), middle = id(x[from] + x[to] >> 1);
      |                                                               ~~~~~~~~^~~~~~~
new_home.cpp:145:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:146:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:150:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:151:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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