답안 #49857 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49857	2018-06-03T21:04:06 Z	zemen	새 집 (APIO18_new_home)	C++17	5 / 100	5000 ms	156412 KB

new_home

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

mt19937 rr(133337);
struct Node {
  int x, y, cnt;
  Node* l;
  Node* r;

  Node(int x) : x(x), y(rr()), cnt(1), l(nullptr), r(nullptr) {}
};

int cnt(Node* t) {
  return t ? t->cnt : 0;
}

void update(Node* t) {
  if (t) {
    t->cnt = cnt(t->l) + cnt(t->r) + 1;
  }
}

void split(Node* t, Node*& l, Node*& r, int x) {
  if (!t) {
    l = r = nullptr;
    return;
  }
  if (t->x >= x) {
    split(t->l, l, t->l, x);
    r = t;
  } else {
    split(t->r, t->r, r, x);
    l = t;
  }
  update(t);
}

void merge(Node*& t, Node* l, Node* r) {
  if (!l) {
    t = r;
  } else if (!r) {
    t = l;
  } else {
    if (l->y > r->y) {
      merge(l->r, l->r, r);
      t = l;
    } else {
      merge(r->l, l, r->l);
      t = r;
    }
    update(t);
  }
}

void ins(Node*& t, int x) {
  Node* A;
  split(t, t, A, x);
  merge(t, t, new Node(x));
  merge(t, t, A);
}

void del(Node*& t, int x) {
  Node* A;
  Node* B;
  split(t, t, B, x + 1);
  split(t, A, t, x);
  assert(t);
  delete t;
  merge(t, A, B);
}

int order_of_key(Node*& t, int x) {
  Node* A;
  split(t, t, A, x);
  int res = cnt(t);
  merge(t, t, A);
  return res;
}

const int base = 1 << 19;
const int inf = 1e9;
Node* t[base * 2];
vector<pair<int, int>> xc;
int k;

int tget(int l, int r, int v = 1, int cl = 0, int cr = base) {
  if (l <= cl && cr <= r) {
    int res = cnt(t[v]) - order_of_key(t[v], r);
    return res;
  }
  if (r <= cl || cr <= l) {
    return 0;
  }
  int cc = (cl + cr) / 2;
  return tget(l, r, v * 2, cl, cc) + tget(l, r, v * 2 + 1, cc, cr);
}

int get(int x) {
  int L = -1, R = inf / 2;
  map<pair<int, int>, int> bscache;
  bool ok = false;
  while (L + 1 < R) {
    int C = (L + R) / 2;
    int lb = lower_bound(xc.begin(), xc.end(), pair<int, int>{x - C, -1}) - xc.begin();
    int rb = upper_bound(xc.begin(), xc.end(), pair<int, int>{x + C, inf}) - xc.begin();

    auto q = pair<int, int>{lb, rb};
    int cnt;
    if (bscache.count(q)) {
      cnt = bscache[q];
    } else {
      bscache[q] = cnt = tget(lb, rb);
    }

    assert(cnt <= k);
    if (cnt == k) {
      R = C;
      ok = true;
    } else {
      L = C;
    }
  }
  if (!ok) {
    return -1;
  } else {
    return R;
  }
}

void tput(int v, int val) {
  v += base;
  while (v >= 1) {
    ins(t[v], val);
    v /= 2;
  }
}

void tdel(int v, int val) {
  v += base;
  while (v >= 1) {
    del(t[v], val);
    v /= 2;
  }
}

set<int> pos[base];
void put(int x, int t, int delta) {
  if (delta == -1) {
    auto it = pos[t].upper_bound(x);
    int val = it == pos[t].end() ? inf + t : *it;
    if (it != pos[t].begin()) {
      --it;
      tdel(*it, val);
      tput(*it, x);
    }
    pos[t].insert(x);
    tput(x, val);
  } else if (delta == 1) {
    assert(pos[t].count(x));
    auto it = pos[t].upper_bound(x);
    int val = it == pos[t].end() ? inf + t : *it;
    tdel(x, val);
    pos[t].erase(x);
    if (it != pos[t].begin()) {
      --it;
      tdel(*it, x);
      tput(*it, val);
    }
  } else {
    assert(false);
  }
}

signed main() {
#ifdef LOCAL
  assert(freopen("a.in", "r", stdin));
#endif
  struct Event {
    int tp, tm, x, t, id;
    bool operator<(const Event& e) const {
      if (tm != e.tm) {
        return tm < e.tm;
      }
      return tp < e.tp;
    }
  };

  int n, q;
  cin >> n >> k >> q;
  vector<Event> ev;
  for (int i = 0; i < n; ++i) {
    int x, t, a, b;
    cin >> x >> t >> a >> b;
    ev.push_back(Event{-1, a, x, t, i});
    ev.push_back(Event{1, b, x, t, i});
    xc.emplace_back(x, i);
  }
  sort(xc.begin(), xc.end());
  for (int i = 0; i < q; ++i) {
    int l, y;
    cin >> l >> y;
    ev.push_back(Event{0, y, l, -1, i});
  }
  sort(ev.begin(), ev.end());
  vector<int> res(q);
  for (auto& e : ev) {
    if (e.tp == 0) {
      res[e.id] = get(e.x);
    } else {
      auto sx = lower_bound(xc.begin(), xc.end(), pair<int, int>{e.x, e.id}) - xc.begin();
      put(sx, e.t, e.tp);
    }
  }
  for (int i = 0; i < q; ++i) {
    cout << res[i] << '\n';
  }
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	24952 KB	Output is correct
2	Correct	25 ms	25060 KB	Output is correct
3	Correct	21 ms	25096 KB	Output is correct
4	Correct	21 ms	25172 KB	Output is correct
5	Correct	33 ms	25376 KB	Output is correct
6	Correct	35 ms	25392 KB	Output is correct
7	Correct	26 ms	25392 KB	Output is correct
8	Correct	31 ms	25648 KB	Output is correct
9	Correct	27 ms	25648 KB	Output is correct
10	Correct	37 ms	25648 KB	Output is correct
11	Correct	27 ms	25648 KB	Output is correct
12	Correct	42 ms	25648 KB	Output is correct
13	Correct	25 ms	25648 KB	Output is correct
14	Correct	26 ms	25648 KB	Output is correct
15	Correct	31 ms	25648 KB	Output is correct
16	Correct	31 ms	25648 KB	Output is correct
17	Correct	33 ms	25648 KB	Output is correct
18	Correct	31 ms	25648 KB	Output is correct
19	Correct	30 ms	25648 KB	Output is correct
20	Correct	30 ms	25648 KB	Output is correct
21	Correct	25 ms	25708 KB	Output is correct
22	Correct	37 ms	25708 KB	Output is correct
23	Correct	35 ms	25708 KB	Output is correct
24	Correct	43 ms	25708 KB	Output is correct
25	Correct	35 ms	25708 KB	Output is correct
26	Correct	30 ms	25708 KB	Output is correct
27	Correct	33 ms	25708 KB	Output is correct
28	Correct	32 ms	25708 KB	Output is correct
29	Correct	32 ms	25708 KB	Output is correct
30	Correct	27 ms	25708 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	24952 KB	Output is correct
2	Correct	25 ms	25060 KB	Output is correct
3	Correct	21 ms	25096 KB	Output is correct
4	Correct	21 ms	25172 KB	Output is correct
5	Correct	33 ms	25376 KB	Output is correct
6	Correct	35 ms	25392 KB	Output is correct
7	Correct	26 ms	25392 KB	Output is correct
8	Correct	31 ms	25648 KB	Output is correct
9	Correct	27 ms	25648 KB	Output is correct
10	Correct	37 ms	25648 KB	Output is correct
11	Correct	27 ms	25648 KB	Output is correct
12	Correct	42 ms	25648 KB	Output is correct
13	Correct	25 ms	25648 KB	Output is correct
14	Correct	26 ms	25648 KB	Output is correct
15	Correct	31 ms	25648 KB	Output is correct
16	Correct	31 ms	25648 KB	Output is correct
17	Correct	33 ms	25648 KB	Output is correct
18	Correct	31 ms	25648 KB	Output is correct
19	Correct	30 ms	25648 KB	Output is correct
20	Correct	30 ms	25648 KB	Output is correct
21	Correct	25 ms	25708 KB	Output is correct
22	Correct	37 ms	25708 KB	Output is correct
23	Correct	35 ms	25708 KB	Output is correct
24	Correct	43 ms	25708 KB	Output is correct
25	Correct	35 ms	25708 KB	Output is correct
26	Correct	30 ms	25708 KB	Output is correct
27	Correct	33 ms	25708 KB	Output is correct
28	Correct	32 ms	25708 KB	Output is correct
29	Correct	32 ms	25708 KB	Output is correct
30	Correct	27 ms	25708 KB	Output is correct
31	Execution timed out	5057 ms	75540 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5071 ms	156412 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5058 ms	156412 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	24952 KB	Output is correct
2	Correct	25 ms	25060 KB	Output is correct
3	Correct	21 ms	25096 KB	Output is correct
4	Correct	21 ms	25172 KB	Output is correct
5	Correct	33 ms	25376 KB	Output is correct
6	Correct	35 ms	25392 KB	Output is correct
7	Correct	26 ms	25392 KB	Output is correct
8	Correct	31 ms	25648 KB	Output is correct
9	Correct	27 ms	25648 KB	Output is correct
10	Correct	37 ms	25648 KB	Output is correct
11	Correct	27 ms	25648 KB	Output is correct
12	Correct	42 ms	25648 KB	Output is correct
13	Correct	25 ms	25648 KB	Output is correct
14	Correct	26 ms	25648 KB	Output is correct
15	Correct	31 ms	25648 KB	Output is correct
16	Correct	31 ms	25648 KB	Output is correct
17	Correct	33 ms	25648 KB	Output is correct
18	Correct	31 ms	25648 KB	Output is correct
19	Correct	30 ms	25648 KB	Output is correct
20	Correct	30 ms	25648 KB	Output is correct
21	Correct	25 ms	25708 KB	Output is correct
22	Correct	37 ms	25708 KB	Output is correct
23	Correct	35 ms	25708 KB	Output is correct
24	Correct	43 ms	25708 KB	Output is correct
25	Correct	35 ms	25708 KB	Output is correct
26	Correct	30 ms	25708 KB	Output is correct
27	Correct	33 ms	25708 KB	Output is correct
28	Correct	32 ms	25708 KB	Output is correct
29	Correct	32 ms	25708 KB	Output is correct
30	Correct	27 ms	25708 KB	Output is correct
31	Execution timed out	5057 ms	75540 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	24952 KB	Output is correct
2	Correct	25 ms	25060 KB	Output is correct
3	Correct	21 ms	25096 KB	Output is correct
4	Correct	21 ms	25172 KB	Output is correct
5	Correct	33 ms	25376 KB	Output is correct
6	Correct	35 ms	25392 KB	Output is correct
7	Correct	26 ms	25392 KB	Output is correct
8	Correct	31 ms	25648 KB	Output is correct
9	Correct	27 ms	25648 KB	Output is correct
10	Correct	37 ms	25648 KB	Output is correct
11	Correct	27 ms	25648 KB	Output is correct
12	Correct	42 ms	25648 KB	Output is correct
13	Correct	25 ms	25648 KB	Output is correct
14	Correct	26 ms	25648 KB	Output is correct
15	Correct	31 ms	25648 KB	Output is correct
16	Correct	31 ms	25648 KB	Output is correct
17	Correct	33 ms	25648 KB	Output is correct
18	Correct	31 ms	25648 KB	Output is correct
19	Correct	30 ms	25648 KB	Output is correct
20	Correct	30 ms	25648 KB	Output is correct
21	Correct	25 ms	25708 KB	Output is correct
22	Correct	37 ms	25708 KB	Output is correct
23	Correct	35 ms	25708 KB	Output is correct
24	Correct	43 ms	25708 KB	Output is correct
25	Correct	35 ms	25708 KB	Output is correct
26	Correct	30 ms	25708 KB	Output is correct
27	Correct	33 ms	25708 KB	Output is correct
28	Correct	32 ms	25708 KB	Output is correct
29	Correct	32 ms	25708 KB	Output is correct
30	Correct	27 ms	25708 KB	Output is correct
31	Execution timed out	5057 ms	75540 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

답안 #49857

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
0 / 35.0

Subtask #6
0 / 20.0