oj.uz

Submission #1007887

# Submission time Handle Problem Language Result Execution time Memory
1007887 2024-06-25T17:02:20 Z LonlyR New Home (APIO18_new_home) C++17
0 / 100
 689 ms 81364 KB 
#include<bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 3e5 + 5;
int n, k, q, cnt;
int mark[maxn], ans[maxn];
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> cur_pos, check;

void add(int id)
{
    auto [pos, type, l, r] = store[id];
    if (mark[type] == 0)
        cnt++;
    cur_pos.emplace(pos);
    mark[type]++;
}

void del(int id)
{
    auto [pos, type, l, r] = store[id];
    if (mark[type] == 1)
        cnt--;
    cur_pos.erase(cur_pos.find(pos));
    mark[type]--;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> k >> q;
    for (int i = 1; i <= n; i++)
    {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        store[i] = {x, t, a, b};
    }
    for (int i = 1, x, t; i <= q; i++)
        cin >> x >> t,
        qr[i] = {t, x, i},
        check.emplace(t);
    for (int i = 1; i <= n; i++)
    {
        auto [x, t, l, r] = store[i];
        if (check.lower_bound(l) == check.upper_bound(r)) continue;
        seg.push_back({x, t, l, r, i});
    }
    sort(seg.begin(), seg.end(),[](array<int, 5> x, array<int, 5> y)
         {
             if (x[2] != y[2]) return x[2] < y[2];
             return x[3] < y[3];
         });
    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 && time <= seg[it][3])
            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 (cnt == k)
        {
            auto it = cur_pos.lower_bound(pos);
            if (it != cur_pos.end())
                ans[id] = max(ans[id], (*it) - pos);
            if (it != cur_pos.begin())
                ans[id] = max(ans[id], pos - (*prev(it)));
        }
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Incorrect 2 ms 2648 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Incorrect 2 ms 2648 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 497 ms 81364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 689 ms 80272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Incorrect 2 ms 2648 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Incorrect 2 ms 2648 KB Output isn't correct
5 Halted 0 ms 0 KB -