답안 #399833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399833	2021-05-06T17:44:14 Z	my99n	새 집 (APIO18_new_home)	C++17	5 / 100	5000 ms	7708 KB

new_home

#include<bits/stdc++.h>
using namespace std;
 
struct event {
  int et, x, t, y, i;
  bool operator < (const event & o) const {
    if (y == o.y) return et < o.et; // open query close
    return y < o.y;
  }
};
vector<event> e;
set<pair<int,int>> s[500];
int ans[100100];
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k, q; cin >> n >> k >> q;
  assert(k < 500);
  for (int i = 1; i <= n; i++) {
    int x, t, a, b; cin >> x >> t >> a >> b;
    e.push_back({1, x, t, a, i});
    e.push_back({3, x, t, b, i});
  }
  for (int i = 1; i <= q; i++) {
    int l, y; cin >> l >> y;
    e.push_back({2, l, 0, y, i});
  }
  sort(e.begin(), e.end());
  for (auto [et, x, t, y, i] : e) {
    if (et == 1) s[t].insert({x, i});
    if (et == 3) s[t].erase({x, i});
    if (et == 2) {
      for (int type = 1; type <= k; type++) {
        if (s[type].empty()) {
          ans[i] = -1;
          break;
        }
        int mn = 1e9;

        for (auto a = s[type].begin(); a != s[type].end(); a++) {
          mn = min(mn, abs(x - a->first));
        }
        // cerr << mn << endl;
        auto lb = s[type].lower_bound({x, -1});
        if (lb == s[type].end()) lb--;
        // cerr << x << ' ' << lb->first << endl;
        assert(mn <= abs(x - (lb->first)));
        mn = min(mn, abs(x-(lb->first)));
        if (lb != s[type].begin()) lb--;
        assert(mn <= abs(x - (lb->first)));
        mn = min(mn, abs(x-(lb->first)));
        // if (a != s[type].end()) mn = min(mn, abs(x-(next(a)->first)));
        // if (a != s[type].begin()) mn = min(mn, abs(x-(prev(a)->first)));

        ans[i] = max(ans[i], mn);
      }
    }
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
  return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7 
4 1 8 10
5 3
5 6 
5 9
1 10
*/

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	3 ms	352 KB	Output is correct
6	Correct	2 ms	436 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	2 ms	332 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	2 ms	332 KB	Output is correct
11	Correct	1 ms	360 KB	Output is correct
12	Correct	2 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	2 ms	332 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct
17	Correct	2 ms	332 KB	Output is correct
18	Correct	2 ms	360 KB	Output is correct
19	Correct	2 ms	332 KB	Output is correct
20	Correct	2 ms	332 KB	Output is correct
21	Correct	4 ms	332 KB	Output is correct
22	Correct	2 ms	332 KB	Output is correct
23	Correct	2 ms	332 KB	Output is correct
24	Correct	2 ms	332 KB	Output is correct
25	Correct	2 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	2 ms	344 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	3 ms	352 KB	Output is correct
6	Correct	2 ms	436 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	2 ms	332 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	2 ms	332 KB	Output is correct
11	Correct	1 ms	360 KB	Output is correct
12	Correct	2 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	2 ms	332 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct
17	Correct	2 ms	332 KB	Output is correct
18	Correct	2 ms	360 KB	Output is correct
19	Correct	2 ms	332 KB	Output is correct
20	Correct	2 ms	332 KB	Output is correct
21	Correct	4 ms	332 KB	Output is correct
22	Correct	2 ms	332 KB	Output is correct
23	Correct	2 ms	332 KB	Output is correct
24	Correct	2 ms	332 KB	Output is correct
25	Correct	2 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	2 ms	344 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Execution timed out	5084 ms	7708 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1 ms	460 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1 ms	460 KB	Execution killed with signal 6
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	3 ms	352 KB	Output is correct
6	Correct	2 ms	436 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	2 ms	332 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	2 ms	332 KB	Output is correct
11	Correct	1 ms	360 KB	Output is correct
12	Correct	2 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	2 ms	332 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct
17	Correct	2 ms	332 KB	Output is correct
18	Correct	2 ms	360 KB	Output is correct
19	Correct	2 ms	332 KB	Output is correct
20	Correct	2 ms	332 KB	Output is correct
21	Correct	4 ms	332 KB	Output is correct
22	Correct	2 ms	332 KB	Output is correct
23	Correct	2 ms	332 KB	Output is correct
24	Correct	2 ms	332 KB	Output is correct
25	Correct	2 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	2 ms	344 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Execution timed out	5084 ms	7708 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	3 ms	352 KB	Output is correct
6	Correct	2 ms	436 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	2 ms	332 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	2 ms	332 KB	Output is correct
11	Correct	1 ms	360 KB	Output is correct
12	Correct	2 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	2 ms	332 KB	Output is correct
16	Correct	2 ms	332 KB	Output is correct
17	Correct	2 ms	332 KB	Output is correct
18	Correct	2 ms	360 KB	Output is correct
19	Correct	2 ms	332 KB	Output is correct
20	Correct	2 ms	332 KB	Output is correct
21	Correct	4 ms	332 KB	Output is correct
22	Correct	2 ms	332 KB	Output is correct
23	Correct	2 ms	332 KB	Output is correct
24	Correct	2 ms	332 KB	Output is correct
25	Correct	2 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	2 ms	344 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Execution timed out	5084 ms	7708 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

답안 #399833

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