Submission #1008331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008331		LonlyR	New Home (APIO18_new_home)	C++17	10 / 100	1981 ms	165336 KiB

new_home

#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(), x.end()

using namespace std;
const int maxn = 6e5 + 5, inf = 1e8;
int n, k, q, cnt, m;
int mark[maxn], ans[maxn];
vector<int> nen;
array<int, 3> qr[maxn];
array<int, 4> store[maxn];
vector<array<int, 5>> seg;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> bound_right;
multiset<int> type[maxn], segment[maxn];
int st[4 * maxn];

void upd(int pos, int id = 1, int l = 1, int r = m)
{
    if (l == r) return void(st[id] = (segment[l].size() ? *segment[r].rbegin() : inf));
    int mid = (l + r) / 2;
    if (pos <= mid) upd(pos, id * 2, l, mid);
    else upd(pos, id * 2 + 1, mid + 1, r);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}

int get(int pos, int id = 1, int l = 1, int r = m)
{
    if (l == r) return st[id];
    int mid = (l + r) / 2;
    if (pos <= mid) return get(pos, id * 2, l, mid);
    return max(st[id * 2], get(pos, id * 2 + 1, mid + 1, r));
}

void add_seg(int l, int r)
{
//    cerr << l << " " << r << " add\n";
    l = upper_bound(all(nen), l) - nen.begin();
    segment[l].emplace(r);
    upd(l);
}

void del_seg(int l, int r)
{
//    cerr << l << " " << r << " del\n";
    l = upper_bound(all(nen), l) - nen.begin();
//    cerr << l << " ??\n";
    segment[l].erase(segment[l].find(r));
    upd(l);
}

set<int> naww;

void add(int id)
{
    auto [x, t, l, r] = store[id];
    l = 1, r = inf;
    auto it = type[t].lower_bound(x);
    if (it != type[t].end()) r = *it - 1;
    if (it != type[t].begin()) l = *prev(it) + 1;
    type[t].emplace(x);
    del_seg(l, r);
    add_seg(l, x - 1);
    add_seg(x + 1, r);
}

void del(int id)
{
    auto [x, t, l, r] = store[id];
    l = 1, r = inf;
    auto it = type[t].lower_bound(x);
    if (next(it) != type[t].end()) r = *next(it) - 1;
    if (it != type[t].begin()) l = *prev(it) + 1;
    type[t].erase(it);
    del_seg(l, x - 1);
    del_seg(x + 1, r);
    add_seg(l, r);
}

int get_ans(int x)
{
    int l = 0, r = inf, ans = -1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        int lx = max(1ll, x - mid), rx = min(inf, x + mid);
        int pos = upper_bound(all(nen), lx) - nen.begin();
        if (get(pos) >= rx) l = mid + 1;
        else ans = mid, r = mid - 1;
    }
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("AC.out", "w", stdout);
    cin >> n >> k >> q;
    nen = {1};
    for (int i = 1; i <= n; i++)
    {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        store[i] = {x, t, a, b};
        nen.emplace_back(x + 1);
    }
    for (int i = 1, x, t; i <= q; i++)
        cin >> x >> t,
        qr[i] = {t, x, i};
//        nen.emplace_back(x);
    sort(all(nen));
    nen.resize(unique(all(nen)) - nen.begin());
    m = nen.size();
    for (int i = 1; i <= n; i++)
    {
        auto [x, t, l, r] = store[i];
        seg.push_back({x, t, l, r, i});
    }
    sort(all(seg),[](array<int, 5> x, array<int, 5> y)
         {
             if (x[2] != y[2]) return x[2] < y[2];
             return x[3] < y[3];
         });
    for (int i = 1; i <= k; i++)
        segment[1].emplace(inf);
    for (int i = 1; i <= m; i++) upd(i);
    sort(qr + 1, qr + q + 1);
    memset(ans, -1, sizeof ans);
    for (int i = 1, it = 0; i <= q; i++)
    {
        auto [time, pos, id] = qr[i];
        while (it < seg.size() && seg[it][2] <= time)
            add(seg[it][4]),
            bound_right.emplace(seg[it][3], seg[it][4]),
            it++;
        while (bound_right.size() && bound_right.top().first < time)
            del(bound_right.top().second),
            bound_right.pop();
//        if (i == 3) {for (int j : naww) cout << j << " dontplay\n";}
        ans[id] = get_ans(pos);
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:133:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 5> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         while (it < seg.size() && seg[it][2] <= time)
      |                ~~~^~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20