Submission #77331

#	Time	Username	Problem	Language	Result	Execution time	Memory
77331		298iq	New Home (APIO18_new_home)	C++14	5 / 100	928 ms	230692 KiB

new_home

#include <bits/stdc++.h>

using namespace std;

const int MEM = 1e8;
char mem[MEM];
int ptr = 0;
void* operator new(size_t n) {
    ptr += n;
    return mem + (ptr - n);
}

void operator delete(void *) {}

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

namespace DD {

struct Node {
    multiset <int> ms;
    Node *l, *r;
    Node() {
        ms = {};
        l = r = NULL;
    }
};

void push(Node *t) {
    if (!t->l) t->l = new Node();
    if (!t->r) t->r = new Node();
}

void add(Node *t, int tl, int tr, int p, int x) {
    t->ms.insert(x);
    if (tl == tr) return;
    int tm = tl + (tr - tl) / 2;
    push(t);
    if (p <= tm) add(t->l, tl, tm, p, x);
    else add(t->r, tm + 1, tr, p, x);
}

void del(Node *t, int tl, int tr, int p, int x) {
    t->ms.erase(t->ms.find(x));
    if (tl == tr) return;
    int tm = tl + (tr - tl) / 2;
    if (p <= tm) del(t->l, tl, tm, p, x);
    else del(t->r, tm + 1, tr, p, x);
}

bool get(Node *t, int tl, int tr, int l, int r, int x) {
    if (tr < l || r < tl) return 0;
    if (l <= tl && tr <= r) return (t->ms.size() && *t->ms.rbegin() >= x);
    int tm = tl + (tr - tl) / 2;
    push(t);
    return get(t->l, tl, tm, l, r, x) || get(t->r, tm + 1, tr, l, r, x);
}

};

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 < q; ++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 = new Node;
multiset <int> ps[MAXN];

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

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

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

bool check(int l, int r) {
    l = max(l, 1);
    r = min(r, MAXV);
    --l; ++r;
    return !get(dd, -INF, INF, -INF, l, 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);
        add(dd, -INF, INF, -INF, INF);
    }

    int u = 0;
    for (int i = 0; i < q; ++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: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20