Submission #77338

#	Time	Username	Problem	Language	Result	Execution time	Memory
77338		298iq	New Home (APIO18_new_home)	C++14	47 / 100	5022 ms	82028 KiB

new_home

#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
 
#include <bits/stdc++.h>
 
using namespace std;
 
/*
const int MEM = 8e8;
char mem[MEM];
int ptr = 0;
void* operator new(size_t n) {
    ptr += n;
    return mem + (ptr - n);
}
*/

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 < 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 = NULL;
multiset <int> ps[MAXN];
 
void add(int c, int p, int num) {
    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, int num) {
    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], 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;
    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 < 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: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 20