Submission #560101

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
560101	2022-05-11T04:06:52 Z	hoanghq2004	New Home (APIO18_new_home)	C++14	10 / 100	797 ms	69756 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7388 KB	Output is correct
2	Incorrect	7 ms	7376 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	7388 KB	Output is correct
2	Incorrect	7 ms	7376 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	745 ms	45972 KB	Output is correct
2	Correct	412 ms	60552 KB	Output is correct
3	Correct	664 ms	69744 KB	Output is correct
4	Correct	797 ms	59784 KB	Output is correct
5	Correct	340 ms	56364 KB	Output is correct
6	Correct	390 ms	56332 KB	Output is correct
7	Correct	577 ms	69756 KB	Output is correct
8	Correct	734 ms	59440 KB	Output is correct
9	Correct	615 ms	58232 KB	Output is correct
10	Correct	506 ms	57496 KB	Output is correct
11	Correct	436 ms	56624 KB	Output is correct
12	Correct	417 ms	57284 KB	Output is correct