oj.uz

Submission #390094

# Submission time Handle Problem Language Result Execution time Memory
390094 2021-04-15T10:32:45 Z phathnv New Home (APIO18_new_home) C++11
33 / 100
 4904 ms 102596 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 * 4 + 1, 0);
    }
    void update(int id, int l, int r, int pos, int val){
        if (pos < l || r < pos)
            return;
        if (l == r){
            d[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, pos, val);
        update(id << 1 | 1, mid + 1, r, pos, val);
        d[id] = max(d[id << 1], d[id << 1 | 1]);
    }
    int getMax(int id, int l, int r, int u, int v){
        if (v < l || r < u)
            return 0;
        if (u <= l && r <= v)
            return d[id];
        int mid = (l + r) >> 1;
        return max(getMax(id << 1, l, mid, u, v), getMax(id << 1 | 1, mid + 1, r, u, v));
    }

    void update(int pos, int val){
        update(1, 1, n, pos, val);
    }
    int getMax(int l, int r){
        return getMax(1, 1, n, l, r);
    }
} 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() + 1;

    ST.init(xCoor.size());
    for(int i = 1; i <= k; i++){
        color[i].insert(i);
        color[i].insert(INF);
        ST.update(i, 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(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() + 1;
                int r = upper_bound(xCoor.begin(), xCoor.end(), Coor(e.x + mid, INF)) - xCoor.begin();
                if (ST.getMax(1, l - 1) <= 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 10 ms 14416 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 10 ms 14416 KB Output is correct
5 Incorrect 10 ms 14424 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 10 ms 14416 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 10 ms 14416 KB Output is correct
5 Incorrect 10 ms 14424 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2786 ms 61352 KB Output is correct
2 Correct 4229 ms 53036 KB Output is correct
3 Correct 2283 ms 102596 KB Output is correct
4 Correct 2625 ms 78884 KB Output is correct
5 Correct 4322 ms 64432 KB Output is correct
6 Correct 4493 ms 64856 KB Output is correct
7 Correct 1983 ms 102548 KB Output is correct
8 Correct 2634 ms 78904 KB Output is correct
9 Correct 3231 ms 70596 KB Output is correct
10 Correct 4067 ms 65872 KB Output is correct
11 Correct 3243 ms 64504 KB Output is correct
12 Correct 3373 ms 65664 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3756 ms 54552 KB Output is correct
2 Correct 970 ms 47464 KB Output is correct
3 Correct 4904 ms 53132 KB Output is correct
4 Correct 2068 ms 100364 KB Output is correct
5 Correct 2606 ms 72020 KB Output is correct
6 Correct 1932 ms 76720 KB Output is correct
7 Correct 4753 ms 64132 KB Output is correct
8 Correct 4759 ms 64556 KB Output is correct
9 Correct 2145 ms 101628 KB Output is correct
10 Correct 2778 ms 75124 KB Output is correct
11 Correct 3198 ms 68300 KB Output is correct
12 Correct 4393 ms 65444 KB Output is correct
13 Correct 3092 ms 63468 KB Output is correct
14 Correct 3035 ms 62644 KB Output is correct
15 Correct 3448 ms 64016 KB Output is correct
16 Correct 3628 ms 65164 KB Output is correct
17 Correct 3493 ms 63756 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 10 ms 14416 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 10 ms 14416 KB Output is correct
5 Incorrect 10 ms 14424 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 10 ms 14416 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 10 ms 14416 KB Output is correct
5 Incorrect 10 ms 14424 KB Output isn't correct
6 Halted 0 ms 0 KB -