Submission #77341

#	Time	Username	Problem	Language	Result	Execution time	Memory
77341		298iq	New Home (APIO18_new_home)	C++14	47 / 100	5011 ms	97896 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 INF = 1e9 + 7;
const int MAXV = 1e8 + 7;
const int D = 2e6; 

namespace DD {
 
mt19937 rnd(228);
    
struct Node {
    pair <int, int> p;
    int y, mx;
    int l, r;
};

int ptr = 0;
Node d[D];

int init(pair <int, int> p) {
    d[ptr].p = p;
    d[ptr].y = rnd();
    d[ptr].mx = p.second;
    d[ptr].l = d[ptr].r = -1;
    ++ptr;
    return ptr - 1;
}
 
int mx(int t) {
    if (t == -1) return -1;
    else return d[t].mx;
}
   
void relax(int t) {
    d[t].mx = max(max(mx(d[t].l), mx(d[t].r)), d[t].p.second);
}
 
int merge(int l, int r) {
    if (l == -1) return r;
    if (r == -1) return l;
    if (d[l].y < d[r].y) {
        d[l].r = merge(d[l].r, r);
        relax(l);
        return l;   
    }
    else {
        d[r].l = merge(l, d[r].l);
        relax(r);
        return r;
    }
}
 
pair <int, int> split(int t, pair <int, int> key) {
    if (t == -1) return {-1, -1};
    if (d[t].p <= key) {
        auto tmp = split(d[t].r, key);
        d[t].r = tmp.first;
        relax(t);
        return {t, tmp.second};
    }
    else {
        auto tmp = split(d[t].l, key);
        d[t].l = tmp.second;
        relax(t);
        return {tmp.first, t};
    }
}
 
int insert(int t, pair <int, int> p) {
    auto tmp = split(t, p);
    return merge(merge(tmp.first, init(p)), tmp.second);
}
 
int erase(int t, pair <int, int> p) {
    auto tmp1 = split(t, p);
    auto tmp2 = split(tmp1.first, {p.first, p.second - 1});
    tmp2.second = merge(d[tmp2.second].l, d[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;
 
int dd = -1;
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