oj.uz

Submission #390110

# Submission time Handle Problem Language Result Execution time Memory
390110 2021-04-15T11:04:22 Z phathnv New Home (APIO18_new_home) C++11
100 / 100
 4348 ms 89996 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 3e5 + 7;
const int INF = 1e9;

struct Coor{
    int x, t;
    Coor(int _x = 0, int _t = 0){
        x = _x;
        t = _t;
    }
    bool operator < (const Coor &oth) const {
        if (x != oth.x)
            return x < oth.x;
        return t < oth.t;
    }
    bool operator == (const Coor &oth) const {
        return (x == oth.x && t == oth.t);
    }
};

struct Event{
    int t, type, x, ind;
    Event(int _t, int _type, int _x, int _ind){
        t = _t;
        type = _type;
        x = _x;
        ind = _ind;
    }
    bool operator < (const Event &oth) const {
        if (t != oth.t)
            return t < oth.t;
        return type < oth.type;
    }
};

struct SegmentTree{
    int n;
    vector<int> d;
    void init(int _n){
        n = _n;
        d.assign(n * 2, 0);
    }
    void update(int pos, int val){
        assert(pos < n);
        pos += n;
        d[pos] = val;
        for(; pos; pos >>= 1)
            d[pos >> 1] = max(d[pos], d[pos ^ 1]);
    }
    int getMax(int l, int r){
        int res = 0;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1){
            if (l & 1)
                res = max(res, d[l++]);
            if (r & 1)
                res = max(res, d[--r]);
        }
        return res;
    }
} ST;

int n, k, q, answer[N];
vector<Coor> xCoor;
vector<Event> events;
multiset<int> color[N];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++){
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        xCoor.push_back(Coor{x, t});
        events.push_back(Event(a, 1, x, t));
        events.push_back(Event(b + 1, -1, x, t));
    }
    for(int i = 1; i <= q; i++){
        int l, y;
        cin >> l >> y;
        events.push_back(Event(y, 2, l, i));
    }
    for(int i = 1; i <= k; i++)
        xCoor.push_back(Coor(-INF, i));
    sort(xCoor.begin(), xCoor.end());
    xCoor.resize(unique(xCoor.begin(), xCoor.end()) - xCoor.begin());
    sort(events.begin(), events.end());
    for(Event &e : events)
        if (e.type != 2)
            e.x = lower_bound(xCoor.begin(), xCoor.end(), Coor(e.x, e.ind)) - xCoor.begin();

    ST.init(xCoor.size());
    for(int i = 1; i <= k; i++){
        color[i].insert(i - 1);
        color[i].insert(INF);
        ST.update(i - 1, INF);
    }
    for(Event e : events)
        if (e.type == -1){
            color[e.ind].erase(color[e.ind].find(e.x));
            auto it = color[e.ind].upper_bound(e.x);
            int r = *it;
            int l = *(--it);
            ST.update(e.x, 0);
            ST.update(l, r);
        } else if (e.type == 1){
            auto it = color[e.ind].upper_bound(e.x);
            int r = *it;
            int l = *(--it);
            ST.update(l, e.x);
            ST.update(e.x, r);
            color[e.ind].insert(e.x);
        } else {
            int lo = 0, hi = 1e8;
            answer[e.ind] = -1;
            while (lo <= hi){
                int mid = (lo + hi) >> 1;
                int l = lower_bound(xCoor.begin(), xCoor.end(), Coor(e.x - mid, -INF)) - xCoor.begin();
                int r = upper_bound(xCoor.begin(), xCoor.end(), Coor(e.x + mid, INF)) - xCoor.begin() - 1;
                if (ST.getMax(0, l) <= r){
                    answer[e.ind] = mid;
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
        }
    for(int i = 1; i <= q; i++)
        cout << answer[i] << '\n';

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14412 KB Output is correct
2 Correct 11 ms 14412 KB Output is correct
3 Correct 11 ms 14412 KB Output is correct
4 Correct 10 ms 14412 KB Output is correct
5 Correct 12 ms 14412 KB Output is correct
6 Correct 12 ms 14372 KB Output is correct
7 Correct 11 ms 14412 KB Output is correct
8 Correct 12 ms 14428 KB Output is correct
9 Correct 13 ms 14512 KB Output is correct
10 Correct 12 ms 14412 KB Output is correct
11 Correct 12 ms 14488 KB Output is correct
12 Correct 11 ms 14388 KB Output is correct
13 Correct 12 ms 14412 KB Output is correct
14 Correct 12 ms 14428 KB Output is correct
15 Correct 13 ms 14380 KB Output is correct
16 Correct 11 ms 14432 KB Output is correct
17 Correct 12 ms 14468 KB Output is correct
18 Correct 11 ms 14412 KB Output is correct
19 Correct 15 ms 14512 KB Output is correct
20 Correct 11 ms 14380 KB Output is correct
21 Correct 12 ms 14484 KB Output is correct
22 Correct 14 ms 14412 KB Output is correct
23 Correct 11 ms 14412 KB Output is correct
24 Correct 11 ms 14412 KB Output is correct
25 Correct 12 ms 14416 KB Output is correct
26 Correct 12 ms 14484 KB Output is correct
27 Correct 11 ms 14412 KB Output is correct
28 Correct 12 ms 14432 KB Output is correct
29 Correct 12 ms 14412 KB Output is correct
30 Correct 11 ms 14412 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14412 KB Output is correct
2 Correct 11 ms 14412 KB Output is correct
3 Correct 11 ms 14412 KB Output is correct
4 Correct 10 ms 14412 KB Output is correct
5 Correct 12 ms 14412 KB Output is correct
6 Correct 12 ms 14372 KB Output is correct
7 Correct 11 ms 14412 KB Output is correct
8 Correct 12 ms 14428 KB Output is correct
9 Correct 13 ms 14512 KB Output is correct
10 Correct 12 ms 14412 KB Output is correct
11 Correct 12 ms 14488 KB Output is correct
12 Correct 11 ms 14388 KB Output is correct
13 Correct 12 ms 14412 KB Output is correct
14 Correct 12 ms 14428 KB Output is correct
15 Correct 13 ms 14380 KB Output is correct
16 Correct 11 ms 14432 KB Output is correct
17 Correct 12 ms 14468 KB Output is correct
18 Correct 11 ms 14412 KB Output is correct
19 Correct 15 ms 14512 KB Output is correct
20 Correct 11 ms 14380 KB Output is correct
21 Correct 12 ms 14484 KB Output is correct
22 Correct 14 ms 14412 KB Output is correct
23 Correct 11 ms 14412 KB Output is correct
24 Correct 11 ms 14412 KB Output is correct
25 Correct 12 ms 14416 KB Output is correct
26 Correct 12 ms 14484 KB Output is correct
27 Correct 11 ms 14412 KB Output is correct
28 Correct 12 ms 14432 KB Output is correct
29 Correct 12 ms 14412 KB Output is correct
30 Correct 11 ms 14412 KB Output is correct
31 Correct 590 ms 23672 KB Output is correct
32 Correct 155 ms 20272 KB Output is correct
33 Correct 629 ms 21628 KB Output is correct
34 Correct 507 ms 21808 KB Output is correct
35 Correct 529 ms 23500 KB Output is correct
36 Correct 590 ms 23484 KB Output is correct
37 Correct 511 ms 21320 KB Output is correct
38 Correct 519 ms 21300 KB Output is correct
39 Correct 454 ms 21340 KB Output is correct
40 Correct 468 ms 21280 KB Output is correct
41 Correct 329 ms 21300 KB Output is correct
42 Correct 284 ms 21324 KB Output is correct
43 Correct 152 ms 23216 KB Output is correct
44 Correct 309 ms 21292 KB Output is correct
45 Correct 337 ms 21296 KB Output is correct
46 Correct 382 ms 21380 KB Output is correct
47 Correct 324 ms 21300 KB Output is correct
48 Correct 351 ms 21292 KB Output is correct
49 Correct 415 ms 21296 KB Output is correct
50 Correct 313 ms 21300 KB Output is correct
51 Correct 402 ms 21328 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2149 ms 59640 KB Output is correct
2 Correct 4308 ms 51728 KB Output is correct
3 Correct 2219 ms 85260 KB Output is correct
4 Correct 2021 ms 63440 KB Output is correct
5 Correct 4261 ms 50804 KB Output is correct
6 Correct 3809 ms 51184 KB Output is correct
7 Correct 1945 ms 85356 KB Output is correct
8 Correct 1997 ms 63372 KB Output is correct
9 Correct 2514 ms 55764 KB Output is correct
10 Correct 3473 ms 51884 KB Output is correct
11 Correct 2596 ms 50868 KB Output is correct
12 Correct 2686 ms 51800 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3119 ms 53168 KB Output is correct
2 Correct 774 ms 48484 KB Output is correct
3 Correct 4074 ms 51732 KB Output is correct
4 Correct 1970 ms 83440 KB Output is correct
5 Correct 2005 ms 57180 KB Output is correct
6 Correct 1851 ms 61652 KB Output is correct
7 Correct 4025 ms 50864 KB Output is correct
8 Correct 4348 ms 51412 KB Output is correct
9 Correct 1999 ms 84624 KB Output is correct
10 Correct 2120 ms 60128 KB Output is correct
11 Correct 2695 ms 53960 KB Output is correct
12 Correct 3722 ms 51704 KB Output is correct
13 Correct 2429 ms 50244 KB Output is correct
14 Correct 2386 ms 49848 KB Output is correct
15 Correct 2592 ms 50768 KB Output is correct
16 Correct 2761 ms 51624 KB Output is correct
17 Correct 2834 ms 50524 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14412 KB Output is correct
2 Correct 11 ms 14412 KB Output is correct
3 Correct 11 ms 14412 KB Output is correct
4 Correct 10 ms 14412 KB Output is correct
5 Correct 12 ms 14412 KB Output is correct
6 Correct 12 ms 14372 KB Output is correct
7 Correct 11 ms 14412 KB Output is correct
8 Correct 12 ms 14428 KB Output is correct
9 Correct 13 ms 14512 KB Output is correct
10 Correct 12 ms 14412 KB Output is correct
11 Correct 12 ms 14488 KB Output is correct
12 Correct 11 ms 14388 KB Output is correct
13 Correct 12 ms 14412 KB Output is correct
14 Correct 12 ms 14428 KB Output is correct
15 Correct 13 ms 14380 KB Output is correct
16 Correct 11 ms 14432 KB Output is correct
17 Correct 12 ms 14468 KB Output is correct
18 Correct 11 ms 14412 KB Output is correct
19 Correct 15 ms 14512 KB Output is correct
20 Correct 11 ms 14380 KB Output is correct
21 Correct 12 ms 14484 KB Output is correct
22 Correct 14 ms 14412 KB Output is correct
23 Correct 11 ms 14412 KB Output is correct
24 Correct 11 ms 14412 KB Output is correct
25 Correct 12 ms 14416 KB Output is correct
26 Correct 12 ms 14484 KB Output is correct
27 Correct 11 ms 14412 KB Output is correct
28 Correct 12 ms 14432 KB Output is correct
29 Correct 12 ms 14412 KB Output is correct
30 Correct 11 ms 14412 KB Output is correct
31 Correct 590 ms 23672 KB Output is correct
32 Correct 155 ms 20272 KB Output is correct
33 Correct 629 ms 21628 KB Output is correct
34 Correct 507 ms 21808 KB Output is correct
35 Correct 529 ms 23500 KB Output is correct
36 Correct 590 ms 23484 KB Output is correct
37 Correct 511 ms 21320 KB Output is correct
38 Correct 519 ms 21300 KB Output is correct
39 Correct 454 ms 21340 KB Output is correct
40 Correct 468 ms 21280 KB Output is correct
41 Correct 329 ms 21300 KB Output is correct
42 Correct 284 ms 21324 KB Output is correct
43 Correct 152 ms 23216 KB Output is correct
44 Correct 309 ms 21292 KB Output is correct
45 Correct 337 ms 21296 KB Output is correct
46 Correct 382 ms 21380 KB Output is correct
47 Correct 324 ms 21300 KB Output is correct
48 Correct 351 ms 21292 KB Output is correct
49 Correct 415 ms 21296 KB Output is correct
50 Correct 313 ms 21300 KB Output is correct
51 Correct 402 ms 21328 KB Output is correct
52 Correct 330 ms 29824 KB Output is correct
53 Correct 302 ms 28076 KB Output is correct
54 Correct 298 ms 25564 KB Output is correct
55 Correct 352 ms 24012 KB Output is correct
56 Correct 337 ms 25692 KB Output is correct
57 Correct 318 ms 21804 KB Output is correct
58 Correct 318 ms 24000 KB Output is correct
59 Correct 333 ms 25388 KB Output is correct
60 Correct 291 ms 21656 KB Output is correct
61 Correct 221 ms 30120 KB Output is correct
62 Correct 339 ms 29952 KB Output is correct
63 Correct 357 ms 26216 KB Output is correct
64 Correct 317 ms 24712 KB Output is correct
65 Correct 288 ms 21988 KB Output is correct
66 Correct 324 ms 21172 KB Output is correct
67 Correct 259 ms 21044 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14412 KB Output is correct
2 Correct 11 ms 14412 KB Output is correct
3 Correct 11 ms 14412 KB Output is correct
4 Correct 10 ms 14412 KB Output is correct
5 Correct 12 ms 14412 KB Output is correct
6 Correct 12 ms 14372 KB Output is correct
7 Correct 11 ms 14412 KB Output is correct
8 Correct 12 ms 14428 KB Output is correct
9 Correct 13 ms 14512 KB Output is correct
10 Correct 12 ms 14412 KB Output is correct
11 Correct 12 ms 14488 KB Output is correct
12 Correct 11 ms 14388 KB Output is correct
13 Correct 12 ms 14412 KB Output is correct
14 Correct 12 ms 14428 KB Output is correct
15 Correct 13 ms 14380 KB Output is correct
16 Correct 11 ms 14432 KB Output is correct
17 Correct 12 ms 14468 KB Output is correct
18 Correct 11 ms 14412 KB Output is correct
19 Correct 15 ms 14512 KB Output is correct
20 Correct 11 ms 14380 KB Output is correct
21 Correct 12 ms 14484 KB Output is correct
22 Correct 14 ms 14412 KB Output is correct
23 Correct 11 ms 14412 KB Output is correct
24 Correct 11 ms 14412 KB Output is correct
25 Correct 12 ms 14416 KB Output is correct
26 Correct 12 ms 14484 KB Output is correct
27 Correct 11 ms 14412 KB Output is correct
28 Correct 12 ms 14432 KB Output is correct
29 Correct 12 ms 14412 KB Output is correct
30 Correct 11 ms 14412 KB Output is correct
31 Correct 590 ms 23672 KB Output is correct
32 Correct 155 ms 20272 KB Output is correct
33 Correct 629 ms 21628 KB Output is correct
34 Correct 507 ms 21808 KB Output is correct
35 Correct 529 ms 23500 KB Output is correct
36 Correct 590 ms 23484 KB Output is correct
37 Correct 511 ms 21320 KB Output is correct
38 Correct 519 ms 21300 KB Output is correct
39 Correct 454 ms 21340 KB Output is correct
40 Correct 468 ms 21280 KB Output is correct
41 Correct 329 ms 21300 KB Output is correct
42 Correct 284 ms 21324 KB Output is correct
43 Correct 152 ms 23216 KB Output is correct
44 Correct 309 ms 21292 KB Output is correct
45 Correct 337 ms 21296 KB Output is correct
46 Correct 382 ms 21380 KB Output is correct
47 Correct 324 ms 21300 KB Output is correct
48 Correct 351 ms 21292 KB Output is correct
49 Correct 415 ms 21296 KB Output is correct
50 Correct 313 ms 21300 KB Output is correct
51 Correct 402 ms 21328 KB Output is correct
52 Correct 2149 ms 59640 KB Output is correct
53 Correct 4308 ms 51728 KB Output is correct
54 Correct 2219 ms 85260 KB Output is correct
55 Correct 2021 ms 63440 KB Output is correct
56 Correct 4261 ms 50804 KB Output is correct
57 Correct 3809 ms 51184 KB Output is correct
58 Correct 1945 ms 85356 KB Output is correct
59 Correct 1997 ms 63372 KB Output is correct
60 Correct 2514 ms 55764 KB Output is correct
61 Correct 3473 ms 51884 KB Output is correct
62 Correct 2596 ms 50868 KB Output is correct
63 Correct 2686 ms 51800 KB Output is correct
64 Correct 3119 ms 53168 KB Output is correct
65 Correct 774 ms 48484 KB Output is correct
66 Correct 4074 ms 51732 KB Output is correct
67 Correct 1970 ms 83440 KB Output is correct
68 Correct 2005 ms 57180 KB Output is correct
69 Correct 1851 ms 61652 KB Output is correct
70 Correct 4025 ms 50864 KB Output is correct
71 Correct 4348 ms 51412 KB Output is correct
72 Correct 1999 ms 84624 KB Output is correct
73 Correct 2120 ms 60128 KB Output is correct
74 Correct 2695 ms 53960 KB Output is correct
75 Correct 3722 ms 51704 KB Output is correct
76 Correct 2429 ms 50244 KB Output is correct
77 Correct 2386 ms 49848 KB Output is correct
78 Correct 2592 ms 50768 KB Output is correct
79 Correct 2761 ms 51624 KB Output is correct
80 Correct 2834 ms 50524 KB Output is correct
81 Correct 330 ms 29824 KB Output is correct
82 Correct 302 ms 28076 KB Output is correct
83 Correct 298 ms 25564 KB Output is correct
84 Correct 352 ms 24012 KB Output is correct
85 Correct 337 ms 25692 KB Output is correct
86 Correct 318 ms 21804 KB Output is correct
87 Correct 318 ms 24000 KB Output is correct
88 Correct 333 ms 25388 KB Output is correct
89 Correct 291 ms 21656 KB Output is correct
90 Correct 221 ms 30120 KB Output is correct
91 Correct 339 ms 29952 KB Output is correct
92 Correct 357 ms 26216 KB Output is correct
93 Correct 317 ms 24712 KB Output is correct
94 Correct 288 ms 21988 KB Output is correct
95 Correct 324 ms 21172 KB Output is correct
96 Correct 259 ms 21044 KB Output is correct
97 Correct 1963 ms 89512 KB Output is correct
98 Correct 748 ms 43304 KB Output is correct
99 Correct 4276 ms 49556 KB Output is correct
100 Correct 1919 ms 81444 KB Output is correct
101 Correct 1871 ms 68424 KB Output is correct
102 Correct 4186 ms 58284 KB Output is correct
103 Correct 3257 ms 46204 KB Output is correct
104 Correct 3449 ms 45532 KB Output is correct
105 Correct 2743 ms 45708 KB Output is correct
106 Correct 2904 ms 45376 KB Output is correct
107 Correct 2005 ms 60308 KB Output is correct
108 Correct 2036 ms 67980 KB Output is correct
109 Correct 1986 ms 49420 KB Output is correct
110 Correct 1901 ms 59220 KB Output is correct
111 Correct 1984 ms 66612 KB Output is correct
112 Correct 1726 ms 48268 KB Output is correct
113 Correct 1167 ms 89996 KB Output is correct
114 Correct 2066 ms 88860 KB Output is correct
115 Correct 2023 ms 69852 KB Output is correct
116 Correct 2021 ms 62280 KB Output is correct
117 Correct 2033 ms 49188 KB Output is correct
118 Correct 2040 ms 44336 KB Output is correct
119 Correct 1362 ms 46852 KB Output is correct
120 Correct 1699 ms 42156 KB Output is correct
121 Correct 2035 ms 42320 KB Output is correct
122 Correct 2150 ms 42136 KB Output is correct
123 Correct 2119 ms 42424 KB Output is correct
124 Correct 1916 ms 42560 KB Output is correct
125 Correct 2376 ms 42748 KB Output is correct
126 Correct 1773 ms 42120 KB Output is correct