Submission #560101

#	Time	Username	Problem	Language	Result	Execution time	Memory
560101		hoanghq2004	New Home (APIO18_new_home)	C++14	10 / 100	797 ms	69756 KiB

new_home

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 3e5 + 10;

int n, k, q;
vector <int> s[N];
int ans[N];

int main() {
//    freopen("test.inp", "r", stdin);
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> q;
    for (int i = 0; i < n; ++i) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        s[t].push_back(x);
    }
    vector <pair <int, int> > work;
    vector <tuple <int, int, int, int> > events;
    for (int i = 1; i <= q; ++i) {
        int x, y;
        cin >> x >> y;
        work.push_back({x * 2, i});
    }
    auto add_line = [&](int x, int y, int a, int b) {
//        cout << x << ' ' << y << ' ' << a << ' ' << b << "aaaaa\n";
        events.push_back({x, -1, a, b});
        events.push_back({y, 1, a, b});
    };
    for (int i = 1; i <= k; ++i) {
        sort(s[i].begin(), s[i].end());
        add_line(- 1e9, s[i].front() * 2, - 1, s[i].front());
        for (int j = 0; j + 1 < s[i].size(); ++j) {
            add_line(s[i][j] * 2, s[i][j] + s[i][j + 1], 1, - s[i][j]);
            add_line(s[i][j] + s[i][j + 1], s[i][j + 1] * 2, - 1, s[i][j + 1]);
        }
        add_line(s[i].back() * 2, 1e9, 1, - s[i].back());
    }
    sort(events.begin(), events.end());
    sort(work.begin(), work.end());
    int i = 0;
    multiset <int> lft, rgt;
    for (auto [x, id]: work) {
        while (i < events.size() && get<0>(events[i]) <= x) {
            auto [_, cmd, a, b] = events[i];
            if (cmd == -1) {
                if (a < 0) lft.insert(b);
                else rgt.insert(b);
            } else {
                if (a < 0) lft.erase(lft.find(b));
                else rgt.erase(rgt.find(b));
            }
            ++i;
        }
        x /= 2;
        ans[id] = 0;
        if (rgt.size()) ans[id] = max(ans[id], x + *(--rgt.end()));
        if (lft.size()) ans[id] = max(ans[id], - x + *(--lft.end()));
    }
    for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:43:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int j = 0; j + 1 < s[i].size(); ++j) {
      |                         ~~~~~~^~~~~~~~~~~~~
new_home.cpp:53:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for (auto [x, id]: work) {
      |               ^
new_home.cpp:54:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         while (i < events.size() && get<0>(events[i]) <= x) {
      |                ~~^~~~~~~~~~~~~~~
new_home.cpp:55:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |             auto [_, cmd, a, b] = events[i];
      |                  ^

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