oj.uz

답안 #1008347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008347 2024-06-26T09:41:00 Z LonlyR 새 집 (APIO18_new_home) C++17
10 / 100
 1923 ms 158816 KB 
#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)
{
//    cout << 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)
{
//    cout << l << " " << r << " del\n";
    l = upper_bound(all(nen), l) - nen.begin();
    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 = max(inf - x, x), 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);
    upd(1);
    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) cout << "---------------\n";
        ans[id] = get_ans(pos);
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:132: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]
  132 |         while (it < seg.size() && seg[it][2] <= time)
      |                ~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 63576 KB Output is correct
2 Correct 21 ms 63620 KB Output is correct
3 Correct 21 ms 63576 KB Output is correct
4 Incorrect 21 ms 63580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 63576 KB Output is correct
2 Correct 21 ms 63620 KB Output is correct
3 Correct 21 ms 63576 KB Output is correct
4 Incorrect 21 ms 63580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1227 ms 140220 KB Output is correct
2 Correct 1883 ms 142820 KB Output is correct
3 Correct 1247 ms 158716 KB Output is correct
4 Correct 1210 ms 149492 KB Output is correct
5 Correct 1837 ms 142476 KB Output is correct
6 Correct 1923 ms 142500 KB Output is correct
7 Correct 1243 ms 158816 KB Output is correct
8 Correct 1089 ms 149360 KB Output is correct
9 Correct 1128 ms 145748 KB Output is correct
10 Correct 1719 ms 143592 KB Output is correct
11 Correct 1264 ms 142316 KB Output is correct
12 Correct 1310 ms 143524 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1858 ms 137408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 63576 KB Output is correct
2 Correct 21 ms 63620 KB Output is correct
3 Correct 21 ms 63576 KB Output is correct
4 Incorrect 21 ms 63580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 63576 KB Output is correct
2 Correct 21 ms 63620 KB Output is correct
3 Correct 21 ms 63576 KB Output is correct
4 Incorrect 21 ms 63580 KB Output isn't correct
5 Halted 0 ms 0 KB -