답안 #66017 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66017	2018-08-09T11:29:24 Z	funcsr	새 집 (APIO18_new_home)	C++17	47 / 100	5000 ms	361368 KB

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

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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	171 ms	175096 KB	Output is correct
2	Correct	177 ms	175404 KB	Output is correct
3	Correct	168 ms	175404 KB	Output is correct
4	Correct	168 ms	175404 KB	Output is correct
5	Correct	169 ms	175404 KB	Output is correct
6	Correct	169 ms	175652 KB	Output is correct
7	Correct	157 ms	175652 KB	Output is correct
8	Correct	156 ms	175652 KB	Output is correct
9	Correct	145 ms	175652 KB	Output is correct
10	Correct	150 ms	175680 KB	Output is correct
11	Correct	145 ms	175680 KB	Output is correct
12	Correct	153 ms	175680 KB	Output is correct
13	Correct	167 ms	175680 KB	Output is correct
14	Correct	160 ms	175680 KB	Output is correct
15	Correct	168 ms	175680 KB	Output is correct
16	Correct	151 ms	175680 KB	Output is correct
17	Correct	164 ms	175680 KB	Output is correct
18	Correct	146 ms	175680 KB	Output is correct
19	Correct	145 ms	175680 KB	Output is correct
20	Correct	158 ms	175680 KB	Output is correct
21	Correct	145 ms	175680 KB	Output is correct
22	Correct	151 ms	175680 KB	Output is correct
23	Correct	149 ms	175680 KB	Output is correct
24	Correct	150 ms	175680 KB	Output is correct
25	Correct	144 ms	175680 KB	Output is correct
26	Correct	149 ms	175680 KB	Output is correct
27	Correct	147 ms	175680 KB	Output is correct
28	Correct	156 ms	175748 KB	Output is correct
29	Correct	156 ms	175748 KB	Output is correct
30	Correct	152 ms	175748 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	171 ms	175096 KB	Output is correct
2	Correct	177 ms	175404 KB	Output is correct
3	Correct	168 ms	175404 KB	Output is correct
4	Correct	168 ms	175404 KB	Output is correct
5	Correct	169 ms	175404 KB	Output is correct
6	Correct	169 ms	175652 KB	Output is correct
7	Correct	157 ms	175652 KB	Output is correct
8	Correct	156 ms	175652 KB	Output is correct
9	Correct	145 ms	175652 KB	Output is correct
10	Correct	150 ms	175680 KB	Output is correct
11	Correct	145 ms	175680 KB	Output is correct
12	Correct	153 ms	175680 KB	Output is correct
13	Correct	167 ms	175680 KB	Output is correct
14	Correct	160 ms	175680 KB	Output is correct
15	Correct	168 ms	175680 KB	Output is correct
16	Correct	151 ms	175680 KB	Output is correct
17	Correct	164 ms	175680 KB	Output is correct
18	Correct	146 ms	175680 KB	Output is correct
19	Correct	145 ms	175680 KB	Output is correct
20	Correct	158 ms	175680 KB	Output is correct
21	Correct	145 ms	175680 KB	Output is correct
22	Correct	151 ms	175680 KB	Output is correct
23	Correct	149 ms	175680 KB	Output is correct
24	Correct	150 ms	175680 KB	Output is correct
25	Correct	144 ms	175680 KB	Output is correct
26	Correct	149 ms	175680 KB	Output is correct
27	Correct	147 ms	175680 KB	Output is correct
28	Correct	156 ms	175748 KB	Output is correct
29	Correct	156 ms	175748 KB	Output is correct
30	Correct	152 ms	175748 KB	Output is correct
31	Correct	3013 ms	245176 KB	Output is correct
32	Correct	382 ms	245176 KB	Output is correct
33	Correct	1918 ms	245176 KB	Output is correct
34	Correct	2877 ms	247184 KB	Output is correct
35	Correct	2855 ms	247184 KB	Output is correct
36	Correct	2113 ms	247184 KB	Output is correct
37	Correct	1748 ms	247184 KB	Output is correct
38	Correct	1487 ms	247184 KB	Output is correct
39	Correct	978 ms	247184 KB	Output is correct
40	Correct	1038 ms	247184 KB	Output is correct
41	Correct	1747 ms	247184 KB	Output is correct
42	Correct	1738 ms	247184 KB	Output is correct
43	Correct	206 ms	247184 KB	Output is correct
44	Correct	1703 ms	247184 KB	Output is correct
45	Correct	1850 ms	247184 KB	Output is correct
46	Correct	1787 ms	247184 KB	Output is correct
47	Correct	843 ms	247184 KB	Output is correct
48	Correct	865 ms	247184 KB	Output is correct
49	Correct	1096 ms	247184 KB	Output is correct
50	Correct	1026 ms	247184 KB	Output is correct
51	Correct	1173 ms	247184 KB	Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	171 ms	175096 KB	Output is correct
2	Correct	177 ms	175404 KB	Output is correct
3	Correct	168 ms	175404 KB	Output is correct
4	Correct	168 ms	175404 KB	Output is correct
5	Correct	169 ms	175404 KB	Output is correct
6	Correct	169 ms	175652 KB	Output is correct
7	Correct	157 ms	175652 KB	Output is correct
8	Correct	156 ms	175652 KB	Output is correct
9	Correct	145 ms	175652 KB	Output is correct
10	Correct	150 ms	175680 KB	Output is correct
11	Correct	145 ms	175680 KB	Output is correct
12	Correct	153 ms	175680 KB	Output is correct
13	Correct	167 ms	175680 KB	Output is correct
14	Correct	160 ms	175680 KB	Output is correct
15	Correct	168 ms	175680 KB	Output is correct
16	Correct	151 ms	175680 KB	Output is correct
17	Correct	164 ms	175680 KB	Output is correct
18	Correct	146 ms	175680 KB	Output is correct
19	Correct	145 ms	175680 KB	Output is correct
20	Correct	158 ms	175680 KB	Output is correct
21	Correct	145 ms	175680 KB	Output is correct
22	Correct	151 ms	175680 KB	Output is correct
23	Correct	149 ms	175680 KB	Output is correct
24	Correct	150 ms	175680 KB	Output is correct
25	Correct	144 ms	175680 KB	Output is correct
26	Correct	149 ms	175680 KB	Output is correct
27	Correct	147 ms	175680 KB	Output is correct
28	Correct	156 ms	175748 KB	Output is correct
29	Correct	156 ms	175748 KB	Output is correct
30	Correct	152 ms	175748 KB	Output is correct
31	Correct	3013 ms	245176 KB	Output is correct
32	Correct	382 ms	245176 KB	Output is correct
33	Correct	1918 ms	245176 KB	Output is correct
34	Correct	2877 ms	247184 KB	Output is correct
35	Correct	2855 ms	247184 KB	Output is correct
36	Correct	2113 ms	247184 KB	Output is correct
37	Correct	1748 ms	247184 KB	Output is correct
38	Correct	1487 ms	247184 KB	Output is correct
39	Correct	978 ms	247184 KB	Output is correct
40	Correct	1038 ms	247184 KB	Output is correct
41	Correct	1747 ms	247184 KB	Output is correct
42	Correct	1738 ms	247184 KB	Output is correct
43	Correct	206 ms	247184 KB	Output is correct
44	Correct	1703 ms	247184 KB	Output is correct
45	Correct	1850 ms	247184 KB	Output is correct
46	Correct	1787 ms	247184 KB	Output is correct
47	Correct	843 ms	247184 KB	Output is correct
48	Correct	865 ms	247184 KB	Output is correct
49	Correct	1096 ms	247184 KB	Output is correct
50	Correct	1026 ms	247184 KB	Output is correct
51	Correct	1173 ms	247184 KB	Output is correct
52	Correct	429 ms	361368 KB	Output is correct
53	Correct	427 ms	361368 KB	Output is correct
54	Correct	1370 ms	361368 KB	Output is correct
55	Correct	1335 ms	361368 KB	Output is correct
56	Correct	1016 ms	361368 KB	Output is correct
57	Correct	1664 ms	361368 KB	Output is correct
58	Correct	1198 ms	361368 KB	Output is correct
59	Correct	1073 ms	361368 KB	Output is correct
60	Correct	1640 ms	361368 KB	Output is correct
61	Correct	237 ms	361368 KB	Output is correct
62	Correct	378 ms	361368 KB	Output is correct
63	Correct	870 ms	361368 KB	Output is correct
64	Correct	1122 ms	361368 KB	Output is correct
65	Correct	1619 ms	361368 KB	Output is correct
66	Correct	1869 ms	361368 KB	Output is correct
67	Correct	508 ms	361368 KB	Output is correct

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	171 ms	175096 KB	Output is correct
2	Correct	177 ms	175404 KB	Output is correct
3	Correct	168 ms	175404 KB	Output is correct
4	Correct	168 ms	175404 KB	Output is correct
5	Correct	169 ms	175404 KB	Output is correct
6	Correct	169 ms	175652 KB	Output is correct
7	Correct	157 ms	175652 KB	Output is correct
8	Correct	156 ms	175652 KB	Output is correct
9	Correct	145 ms	175652 KB	Output is correct
10	Correct	150 ms	175680 KB	Output is correct
11	Correct	145 ms	175680 KB	Output is correct
12	Correct	153 ms	175680 KB	Output is correct
13	Correct	167 ms	175680 KB	Output is correct
14	Correct	160 ms	175680 KB	Output is correct
15	Correct	168 ms	175680 KB	Output is correct
16	Correct	151 ms	175680 KB	Output is correct
17	Correct	164 ms	175680 KB	Output is correct
18	Correct	146 ms	175680 KB	Output is correct
19	Correct	145 ms	175680 KB	Output is correct
20	Correct	158 ms	175680 KB	Output is correct
21	Correct	145 ms	175680 KB	Output is correct
22	Correct	151 ms	175680 KB	Output is correct
23	Correct	149 ms	175680 KB	Output is correct
24	Correct	150 ms	175680 KB	Output is correct
25	Correct	144 ms	175680 KB	Output is correct
26	Correct	149 ms	175680 KB	Output is correct
27	Correct	147 ms	175680 KB	Output is correct
28	Correct	156 ms	175748 KB	Output is correct
29	Correct	156 ms	175748 KB	Output is correct
30	Correct	152 ms	175748 KB	Output is correct
31	Correct	3013 ms	245176 KB	Output is correct
32	Correct	382 ms	245176 KB	Output is correct
33	Correct	1918 ms	245176 KB	Output is correct
34	Correct	2877 ms	247184 KB	Output is correct
35	Correct	2855 ms	247184 KB	Output is correct
36	Correct	2113 ms	247184 KB	Output is correct
37	Correct	1748 ms	247184 KB	Output is correct
38	Correct	1487 ms	247184 KB	Output is correct
39	Correct	978 ms	247184 KB	Output is correct
40	Correct	1038 ms	247184 KB	Output is correct
41	Correct	1747 ms	247184 KB	Output is correct
42	Correct	1738 ms	247184 KB	Output is correct
43	Correct	206 ms	247184 KB	Output is correct
44	Correct	1703 ms	247184 KB	Output is correct
45	Correct	1850 ms	247184 KB	Output is correct
46	Correct	1787 ms	247184 KB	Output is correct
47	Correct	843 ms	247184 KB	Output is correct
48	Correct	865 ms	247184 KB	Output is correct
49	Correct	1096 ms	247184 KB	Output is correct
50	Correct	1026 ms	247184 KB	Output is correct
51	Correct	1173 ms	247184 KB	Output is correct
52	Execution timed out	5036 ms	361368 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-

답안 #66017

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 35.0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
35.0 / 35.0

Subtask #6
0 / 20.0