Submission #905757

#	Time	Username	Problem	Language	Result	Execution time	Memory
905757		nguyentunglam	New Home (APIO18_new_home)	C++17	47 / 100	5037 ms	373796 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;

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];

set<pair<int, int> > s[N];

bool alive[N * 3];

bool bug;

struct IT {
  int type;
  priority_queue<pair<int, int> > T[N << 2];
  void up(int s, int l, int r, int from, int to, pair<int, int> tmp) {
    if (l > to || r < from) return;
    if (from <= l && r <= to) {
      T[s].push(tmp);
      return;
    }
    int mid = l + r >> 1;
    up(s << 1, l, mid, from, to, tmp);
    up(s << 1 | 1, mid + 1, r, from, to, tmp);
  }

  int get(int s, int l, int r, int pos, int _pos) {
    int ret = 0;
    while (!T[s].empty()) {
      int i = T[s].top().second;
      int j = type ? pre[i] : nxt[i];
//      cout << abs(x[i] - _pos) << " " << abs(x[j] - _pos) << endl;
      if (alive[i] == 0 || abs(x[i] - _pos) > abs(x[j] - _pos)) T[s].pop();
      else if (x[i] == x[j]) T[s].pop();
      else {
//        cout << i << " " << j << " " << type << " " << pre[4] << " " << alive[i] << endl;
        ret = max(ret, abs(x[i] - _pos));
//        if (type) cout << x[i] << " " << i << " " << abs(x[i] - _pos) << " " << j << endl;
        break;
      }
    }
//    if (bug) {
//      if (!T[s].empty()) cout << T[s].top().second << endl;
//    }
    if (l == r) return ret;
    int mid = l + r >> 1;
    if (pos <= mid) return max(ret, get(s << 1, l, mid, pos, _pos));
    return max(ret, get(s << 1 | 1, mid + 1, r, pos, _pos));
  }
} it[2];

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

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

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);
  }

  it[0].type = 0;
  it[1].type = 1;

  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;
  int sz = rrh.size();

  for(int i = 1; i <= k; i++) {
    x[cnt + 1] = -1e9;
    x[cnt + 2] = 1e9;
    alive[cnt + 1] = alive[cnt + 2] = 1;
    s[i].insert({x[cnt + 1], cnt + 1});
    s[i].insert({x[cnt + 2], cnt + 2});
    it[1].up(1, 1, sz, 1, sz, make_pair(x[cnt + 2], cnt + 2));
    nxt[cnt + 1] = cnt + 2;
    pre[cnt + 2] = cnt + 1;
    cnt += 2;
  }

  for(int cur = 1; cur <= m; cur++) {
    for(int &j : open[cur]) {
      auto iter = s[t[j]].lower_bound(make_pair(x[j], j));
      int to = iter -> second;
      --iter;
      int from = iter -> second;
      int L = id(x[from] - 1) + 1, R = id(x[to]), pos = id(x[j]);
      int middle;
      middle = id(x[from] + x[j] >> 1);

//      if (j == 1) cout << from << " " << to << endl;

      it[0].up(1, 1, sz, L, middle, make_pair(-x[from], from));
      it[1].up(1, 1, sz, middle + 1, pos, make_pair(x[j], j));

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

      it[0].up(1, 1, sz, pos, middle, make_pair(-x[j], j));
      it[1].up(1, 1, sz, middle + 1, R, make_pair(x[to], to));

//      cout << pos << " " << middle << endl;


      nxt[from] = j;
      pre[j] = from;
      nxt[j] = to;
      pre[to] = j;
      s[t[j]].insert({x[j], j});
      alive[j] = 1;
    }
    for(int &j : event[cur]) {
      int cost1 = it[0].get(1, 1, sz, id(c[j]), c[j]);
      int cost2 = it[1].get(1, 1, sz, id(c[j]), c[j]);
//      cout << cost1 << " " << cost2 << endl;
      ans[j] = max(cost1, cost2);
    }
    for(int &j : close[cur]) {
      auto iter = s[t[j]].find(make_pair(x[j], j));
      ++iter;
      int to = iter -> second;
      --iter; --iter;
      int from = iter -> second;

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

      it[0].up(1, 1, sz, L, middle, make_pair(-x[from], from));
      it[1].up(1, 1, sz, middle + 1, R, make_pair(x[to], to));
//      cout << from << " " << to << endl;
//      cout << L << " " << middle << " " << x[from] << endl;
//      cout << middle + 1 << " " << R << " " << x[to] << endl;
      nxt[from] = to;
      pre[to] = from;
      s[t[j]].erase(s[t[j]].find(make_pair(x[j], j)));
      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 member function 'void IT::up(int, int, int, int, int, std::pair<int, int>)':
new_home.cpp:31:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In member function 'int IT::get(int, int, int, int, int)':
new_home.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int mid = l + r >> 1;
      |               ~~^~~
new_home.cpp: In function 'int32_t main()':
new_home.cpp:143:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  143 |       middle = id(x[from] + x[j] >> 1);
      |                   ~~~~~~~~^~~~~~
new_home.cpp:150:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  150 |       middle = id(x[j] + x[to] >> 1);
      |                   ~~~~~^~~~~~~
new_home.cpp:179:71: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  179 |       int L = id(x[from] - 1) + 1, R = id(x[to]), middle = id(x[from] + x[to] >> 1);
      |                                                               ~~~~~~~~^~~~~~~
new_home.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:81:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:82:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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