oj.uz

Submission #77320

# Submission time Handle Problem Language Result Execution time Memory
77320 2018-09-25T17:32:22 Z 298iq New Home (APIO18_new_home) C++14
0 / 100
 5000 ms 108676 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int INF = 1e9 + 7;
const int MAXV = 1e8 + 7;

namespace DD {

mt19937 rnd(228);
    
struct Node {
    pair <int, int> p;
    int y, mx;
    Node *l, *r;
    Node(pair <int, int> p_) {
        p = p_; y = rnd(); mx = p.second;
        l = r = NULL;
    }
    Node(){}
};

int mx(Node *t) {
    if (!t) return -1;
    else return t->mx;
}
   
void relax(Node *t) {
    t->mx = max(max(mx(t->l), mx(t->r)), t->p.second);
}

Node *merge(Node *l, Node *r) {
    if (!l) return r;
    if (!r) return l;
    if (l->y < r->y) {
        l->r = merge(l->r, r);
        relax(l);
        return l;   
    }
    else {
        r->l = merge(l, r->l);
        relax(r);
        return r;
    }
}

pair <Node*, Node*> split(Node *t, pair <int, int> key) {
    if (!t) return {NULL, NULL};
    if (t->p <= key) {
        auto tmp = split(t->r, key);
        t->r = tmp.first;
        relax(t);
        return {t, tmp.second};
    }
    else {
        auto tmp = split(t->l, key);
        t->l = tmp.second;
        relax(t);
        return {tmp.first, t};
    }
}

Node *insert(Node *t, pair <int, int> p) {
    auto tmp = split(t, p);
    return merge(merge(tmp.first, new Node(p)), tmp.second);
}

Node *erase(Node *t, pair <int, int> p) {
    auto tmp1 = split(t, p);
    auto tmp2 = split(tmp1.first, {p.first, p.second - 1});
    tmp2.second = merge(tmp2.second->l, tmp2.second->r);
    return merge(merge(tmp2.first, tmp2.second), tmp1.second);
}
};

const int MAXN = 3e5 + 7;

int n, k, q;
int p[MAXN], c[MAXN], l[MAXN], r[MAXN];
int p2[MAXN], t2[MAXN];
void read() {
    cin >> n >> k >> q;
    for (int i = 0; i < n; ++i) {
        cin >> p[i] >> c[i] >> l[i] >> r[i];
        --c[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> p2[i] >> t2[i];
    }
}

struct Event {
    bool type;
    int t, i;
    Event(bool type_, int t_, int i_) {
        type = type_; t = t_; i = i_;
    }
    Event(){}
};

bool comp(Event a, Event b) {
    return a.t < b.t;
}

int ans[MAXN];
int qper[MAXN];

bool comp1(int i, int j) {
    return t2[i] < t2[j];
}

using namespace DD;

Node *dd = NULL;
set <int> ps[MAXN];

void add(int c, int p) {
    auto r = ps[c].lower_bound(p);
    auto l = r; --l;
    dd = erase(dd, {*l, *r});
    dd = insert(dd, {*l, p});
    dd = insert(dd, {p, *r});
    ps[c].insert(p);
}

void del(int c, int p) {
    auto it = ps[c].lower_bound(p);
    auto l = it; --l;
    auto r = it; ++r;
    dd = erase(dd, {*l, p});
    dd = erase(dd, {p, *r});
    dd = insert(dd, {*l, *r});
    ps[c].erase(it);
}

void upd(Event e) {
    if (e.type) {
        add(c[e.i], p[e.i]);
    }
    else {
        del(c[e.i], p[e.i]);
    }
}

bool check(int l, int r) {
    l = max(l, 1ll);
    r = min(r, MAXV);
    --l; ++r;
    auto tmp = split(dd, {l, INF});
    int res = mx(tmp.first);
    dd = merge(tmp.first, tmp.second);
    return (res < r);
}

int get(int p) {
    if (!check(1, MAXV)) return -1;
    int l = -1;
    int r = MAXV;
    while (l < r - 1) {
        int m = (l + r) / 2;
        if (!check(p - m, p + m)) l = m;
        else r = m;
    }
    return r;
}

void solve() {
    vector <Event> v;
    for (int i = 0; i < n; ++i) {
        v.push_back(Event(1, l[i], i));
        v.push_back(Event(0, r[i] + 1, i));
    }
    sort(v.begin(), v.end(), comp);

    for (int i = 0; i < q; ++i) qper[i] = i;
    sort(qper, qper + q, comp1);

    for (int i = 0; i < k; ++i) {
        ps[i].insert(-INF);
        ps[i].insert(INF);
        dd = insert(dd, {-INF, INF});
    }

    int u = 0;
    for (int i = 0; i < n; ++i) {
        while (u < (int)v.size() && v[u].t <= t2[qper[i]]) {
            upd(v[u]);
            ++u;
        }   
        ans[qper[i]] = get(p2[qper[i]]);
    }
}

void print() {
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
}

signed main() {
    //freopen("input.txt", "r", stdin);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    read();
    solve();
    print();

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 15 ms 14588 KB Output is correct
3 Incorrect 14 ms 14760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 15 ms 14588 KB Output is correct
3 Incorrect 14 ms 14760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4932 ms 108676 KB Output is correct
2 Execution timed out 5044 ms 108676 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 15 ms 14588 KB Output is correct
3 Incorrect 14 ms 14760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 15 ms 14588 KB Output is correct
3 Incorrect 14 ms 14760 KB Output isn't correct
4 Halted 0 ms 0 KB -