oj.uz

Submission #546753

# Submission time Handle Problem Language Result Execution time Memory
546753 2022-04-08T12:02:32 Z Monarchuwu New Home (APIO18_new_home) C++17
12 / 100
 5000 ms 57516 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;

const int N = 3e5 + 7, inf = 1e9 + 7;
int n, k, q, cnt;
struct Data {
    int x, type, time, op;
    Data() {}
    Data(int x, int type, int time, int op) : x(x), type(type), time(time), op(op) {}
    bool operator < (const Data &o) const {
        if (time != o.time) return time < o.time;
        return op > o.op;
    }
} a[N * 3];

multiset<int> s[N];
int ans[N];
void solve() {
    for (int i = 1, id; i <= cnt; ++i) {
        id = a[i].type;
        if (a[i].op == 1)
            s[id].insert(a[i].x);
        else if (a[i].op == -1)
            s[id].erase(s[id].find(a[i].x));
        else {
            for (int j = 1; j <= k; ++j) {
                if (s[j].empty()) { ans[id] = -1; break; }

                int dist(inf);
                multiset<int>::iterator it = s[j].lower_bound(a[i].x);
                if (it != s[j].end()) dist = min(dist, *it - a[i].x);
                if (it != s[j].begin()) dist = min(dist, a[i].x - *(--it));
                ans[id] = max(ans[id], dist);
            }
        }
    }
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> k >> q;
    for (int i = 0, x, t, l, r; i < n; ++i) {
        cin >> x >> t >> l >> r;
        a[++cnt] = Data(x, t, l, 1);
        a[++cnt] = Data(x, t, r, -1);
    }
    for (int i = 0; i < q; ++i) {
        int l, y; cin >> l >> y;
        a[++cnt] = Data(l, i, y, 0);
    }

    sort(a + 1, a + cnt + 1);
    solve();
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 8 ms 14392 KB Output is correct
3 Correct 8 ms 14440 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 9 ms 14456 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14444 KB Output is correct
9 Correct 8 ms 14460 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14440 KB Output is correct
12 Correct 8 ms 14444 KB Output is correct
13 Correct 13 ms 14360 KB Output is correct
14 Correct 8 ms 14420 KB Output is correct
15 Correct 8 ms 14444 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 8 ms 14448 KB Output is correct
18 Correct 8 ms 14444 KB Output is correct
19 Correct 7 ms 14444 KB Output is correct
20 Correct 8 ms 14436 KB Output is correct
21 Correct 8 ms 14416 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 8 ms 14448 KB Output is correct
24 Correct 8 ms 14420 KB Output is correct
25 Correct 9 ms 14420 KB Output is correct
26 Correct 8 ms 14564 KB Output is correct
27 Correct 7 ms 14420 KB Output is correct
28 Correct 8 ms 14440 KB Output is correct
29 Correct 7 ms 14444 KB Output is correct
30 Correct 9 ms 14444 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 8 ms 14392 KB Output is correct
3 Correct 8 ms 14440 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 9 ms 14456 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14444 KB Output is correct
9 Correct 8 ms 14460 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14440 KB Output is correct
12 Correct 8 ms 14444 KB Output is correct
13 Correct 13 ms 14360 KB Output is correct
14 Correct 8 ms 14420 KB Output is correct
15 Correct 8 ms 14444 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 8 ms 14448 KB Output is correct
18 Correct 8 ms 14444 KB Output is correct
19 Correct 7 ms 14444 KB Output is correct
20 Correct 8 ms 14436 KB Output is correct
21 Correct 8 ms 14416 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 8 ms 14448 KB Output is correct
24 Correct 8 ms 14420 KB Output is correct
25 Correct 9 ms 14420 KB Output is correct
26 Correct 8 ms 14564 KB Output is correct
27 Correct 7 ms 14420 KB Output is correct
28 Correct 8 ms 14440 KB Output is correct
29 Correct 7 ms 14444 KB Output is correct
30 Correct 9 ms 14444 KB Output is correct
31 Correct 1787 ms 23596 KB Output is correct
32 Correct 84 ms 19648 KB Output is correct
33 Correct 154 ms 21868 KB Output is correct
34 Correct 1399 ms 21904 KB Output is correct
35 Correct 811 ms 23640 KB Output is correct
36 Correct 183 ms 23536 KB Output is correct
37 Correct 151 ms 20940 KB Output is correct
38 Correct 87 ms 20808 KB Output is correct
39 Correct 80 ms 20592 KB Output is correct
40 Correct 101 ms 20580 KB Output is correct
41 Correct 231 ms 20920 KB Output is correct
42 Correct 182 ms 20708 KB Output is correct
43 Correct 254 ms 23132 KB Output is correct
44 Correct 193 ms 20940 KB Output is correct
45 Correct 108 ms 20868 KB Output is correct
46 Correct 87 ms 20848 KB Output is correct
47 Correct 62 ms 20308 KB Output is correct
48 Correct 61 ms 20376 KB Output is correct
49 Correct 75 ms 20520 KB Output is correct
50 Correct 170 ms 20684 KB Output is correct
51 Correct 65 ms 20492 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5065 ms 57516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5102 ms 56744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 8 ms 14392 KB Output is correct
3 Correct 8 ms 14440 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 9 ms 14456 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14444 KB Output is correct
9 Correct 8 ms 14460 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14440 KB Output is correct
12 Correct 8 ms 14444 KB Output is correct
13 Correct 13 ms 14360 KB Output is correct
14 Correct 8 ms 14420 KB Output is correct
15 Correct 8 ms 14444 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 8 ms 14448 KB Output is correct
18 Correct 8 ms 14444 KB Output is correct
19 Correct 7 ms 14444 KB Output is correct
20 Correct 8 ms 14436 KB Output is correct
21 Correct 8 ms 14416 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 8 ms 14448 KB Output is correct
24 Correct 8 ms 14420 KB Output is correct
25 Correct 9 ms 14420 KB Output is correct
26 Correct 8 ms 14564 KB Output is correct
27 Correct 7 ms 14420 KB Output is correct
28 Correct 8 ms 14440 KB Output is correct
29 Correct 7 ms 14444 KB Output is correct
30 Correct 9 ms 14444 KB Output is correct
31 Correct 1787 ms 23596 KB Output is correct
32 Correct 84 ms 19648 KB Output is correct
33 Correct 154 ms 21868 KB Output is correct
34 Correct 1399 ms 21904 KB Output is correct
35 Correct 811 ms 23640 KB Output is correct
36 Correct 183 ms 23536 KB Output is correct
37 Correct 151 ms 20940 KB Output is correct
38 Correct 87 ms 20808 KB Output is correct
39 Correct 80 ms 20592 KB Output is correct
40 Correct 101 ms 20580 KB Output is correct
41 Correct 231 ms 20920 KB Output is correct
42 Correct 182 ms 20708 KB Output is correct
43 Correct 254 ms 23132 KB Output is correct
44 Correct 193 ms 20940 KB Output is correct
45 Correct 108 ms 20868 KB Output is correct
46 Correct 87 ms 20848 KB Output is correct
47 Correct 62 ms 20308 KB Output is correct
48 Correct 61 ms 20376 KB Output is correct
49 Correct 75 ms 20520 KB Output is correct
50 Correct 170 ms 20684 KB Output is correct
51 Correct 65 ms 20492 KB Output is correct
52 Correct 85 ms 23492 KB Output is correct
53 Correct 67 ms 21692 KB Output is correct
54 Correct 119 ms 23432 KB Output is correct
55 Execution timed out 5055 ms 21436 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 8 ms 14392 KB Output is correct
3 Correct 8 ms 14440 KB Output is correct
4 Correct 8 ms 14416 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 9 ms 14456 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 8 ms 14444 KB Output is correct
9 Correct 8 ms 14460 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14440 KB Output is correct
12 Correct 8 ms 14444 KB Output is correct
13 Correct 13 ms 14360 KB Output is correct
14 Correct 8 ms 14420 KB Output is correct
15 Correct 8 ms 14444 KB Output is correct
16 Correct 8 ms 14420 KB Output is correct
17 Correct 8 ms 14448 KB Output is correct
18 Correct 8 ms 14444 KB Output is correct
19 Correct 7 ms 14444 KB Output is correct
20 Correct 8 ms 14436 KB Output is correct
21 Correct 8 ms 14416 KB Output is correct
22 Correct 8 ms 14420 KB Output is correct
23 Correct 8 ms 14448 KB Output is correct
24 Correct 8 ms 14420 KB Output is correct
25 Correct 9 ms 14420 KB Output is correct
26 Correct 8 ms 14564 KB Output is correct
27 Correct 7 ms 14420 KB Output is correct
28 Correct 8 ms 14440 KB Output is correct
29 Correct 7 ms 14444 KB Output is correct
30 Correct 9 ms 14444 KB Output is correct
31 Correct 1787 ms 23596 KB Output is correct
32 Correct 84 ms 19648 KB Output is correct
33 Correct 154 ms 21868 KB Output is correct
34 Correct 1399 ms 21904 KB Output is correct
35 Correct 811 ms 23640 KB Output is correct
36 Correct 183 ms 23536 KB Output is correct
37 Correct 151 ms 20940 KB Output is correct
38 Correct 87 ms 20808 KB Output is correct
39 Correct 80 ms 20592 KB Output is correct
40 Correct 101 ms 20580 KB Output is correct
41 Correct 231 ms 20920 KB Output is correct
42 Correct 182 ms 20708 KB Output is correct
43 Correct 254 ms 23132 KB Output is correct
44 Correct 193 ms 20940 KB Output is correct
45 Correct 108 ms 20868 KB Output is correct
46 Correct 87 ms 20848 KB Output is correct
47 Correct 62 ms 20308 KB Output is correct
48 Correct 61 ms 20376 KB Output is correct
49 Correct 75 ms 20520 KB Output is correct
50 Correct 170 ms 20684 KB Output is correct
51 Correct 65 ms 20492 KB Output is correct
52 Execution timed out 5065 ms 57516 KB Time limit exceeded
53 Halted 0 ms 0 KB -