oj.uz

Submission #412620

# Submission time Handle Problem Language Result Execution time Memory
412620 2021-05-27T08:02:56 Z dolphingarlic New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 225640 KB 
/*
APIO 2018 New Home
- Consider the case where all stores are always active
- We basically want the maximum of a bunch of "broken absolute value" graphs
- Consider the positive and negative slopes separately
- If we do this, then we get a bunch of line segments
- WLOG, extend the line segments into rays that go below the x-axis
- Since all slopes are equal, we only need to store the x-intersect of each ray
- Queries thus become prefix maximum queries (i.e. maximum ray that starts
  before the queried position)
- We can handle this using a simple segment tree
- To handle the general case, notice that there are O(N) possible rays, each
  with a period of relevance
- We can thus create a second segment tree indexed on time, where each leaf
  is a query, and DFS on that tree to update our first segment tree
- We can avoid an additional log N factor by keeping an array of sets that
  store "hidden" values at each point
- Complexity: O(N log N)
*/

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int INF = 1e8;

vector<int> c_loc, c_time;
map<int, vector<pair<int, int>>> queries, toggle, ins, del;
vector<tuple<int, int, int>> stores[300001];
int ans[300001], segtree[1200001];
multiset<int> rays[300001];

int query(int loc, int node = 1, int l = 0, int r = c_loc.size() - 1) {
    if (r <= loc) return segtree[node];
    if (l > loc) return -1;
    int mid = (l + r) / 2;
    return max(query(loc, node * 2, l, mid),
               query(loc, node * 2 + 1, mid + 1, r));
}

void update(int loc, int val, int node = 1, int l = 0,
            int r = c_loc.size() - 1) {
    if (l == r)
        segtree[node] = val;
    else {
        int mid = (l + r) / 2;
        if (loc > mid)
            update(loc, val, node * 2 + 1, mid + 1, r);
        else
            update(loc, val, node * 2, l, mid);
        segtree[node] = max(segtree[node * 2], segtree[node * 2 + 1]);
    }
}

void ins_ray(int loc, int val) {
    if (loc == c_loc.size()) return;
    // cout << "INS " << loc << ' ' << val << ' ' << rays[loc].size() << endl;
    rays[loc].insert(val);
    update(loc, *rays[loc].rbegin());
}

void del_ray(int loc, int val) {
    if (loc == c_loc.size()) return;
    // cout << "DEL " << loc << ' ' << val << ' ' << rays[loc].size() << endl;
    rays[loc].erase(rays[loc].find(val));
    update(loc, *rays[loc].rbegin());
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, k, q;
    cin >> n >> k >> q;
    for (int i = 1; i <= n; i++) {
        int loc, type, a, b;
        cin >> loc >> type >> a >> b;
        stores[type].push_back({a, loc, 0});
        stores[type].push_back({b + 1, loc, 1});
    }
    for (int i = 1; i <= q; i++) {
        int loc, time;
        cin >> loc >> time;
        c_loc.push_back(2 * loc);
        c_time.push_back(time);
        queries[time].push_back({i, loc});
        ans[i] = -1;
    }
    sort(c_loc.begin(), c_loc.end());
    c_loc.erase(unique(c_loc.begin(), c_loc.end()), c_loc.end());
    sort(c_time.begin(), c_time.end());
    c_time.erase(unique(c_time.begin(), c_time.end()), c_time.end());
    c_time.push_back(INF + 1);

    for (int _ : {0, 1}) {
        for (int i = 0; i < c_loc.size(); i++) {
            rays[i].clear();
            rays[i].insert(-INF);
        }

        for (int t = 1; t <= k; t++) {
            // cout << "Store type " << t << endl;
            sort(stores[t].begin(), stores[t].end());
            map<int, int> active, ray_at;
            for (auto i : stores[t]) {
                int time, loc, close;
                tie(time, loc, close) = i;
                time = *lower_bound(c_time.begin(), c_time.end(), time);
                // cout << time << ' ' << loc << ' ' << close << endl;
                if (close) {
                    active[loc]--;
                    if (!active[loc]) {
                        active.erase(loc);
                        auto ub = active.upper_bound(loc);
                        del[time].push_back({ray_at[loc], loc});
                        ray_at.erase(loc);
                        if (ub != active.end()) {
                            del[time].push_back({ray_at[ub->first], ub->first});
                            if (ub != active.begin()) {
                                ins[time].push_back(
                                    {prev(ub)->first + ub->first, ub->first});
                                ray_at[ub->first] = prev(ub)->first + ub->first;
                            } else {
                                ins[time].push_back({0, ub->first});
                                ray_at[ub->first] = 0;
                            }
                        }
                    }
                } else {
                    if (!active.count(loc)) {
                        auto ub = active.upper_bound(loc);
                        if (ub != active.end()) {
                            del[time].push_back({ray_at[ub->first], ub->first});
                            ins[time].push_back({ub->first + loc, ub->first});
                            ray_at[ub->first] = ub->first + loc;
                        }
                        if (ub != active.begin()) {
                            ins[time].push_back({loc + prev(ub)->first, loc});
                            ray_at[loc] = loc + prev(ub)->first;
                        } else {
                            ins[time].push_back({0, loc});
                            ray_at[loc] = 0;
                        }
                    }
                    active[loc]++;
                }
                toggle[time].push_back({t, 1 - 2 * close});
            }
        }

        // cout << "=== c_loc ===\n";
        // for (int i : c_loc) cout << i << ' ';
        // cout << endl;
        // cout << "=== INSERT ===\n";
        // for (auto& i : ins) {
        //     cout << i.first << ": ";
        //     for (auto& j : i.second)
        //         cout << '(' << j.first << ", " << j.second << ") ";
        //     cout << endl;
        // }
        // cout << "=== DELETE ===\n";
        // for (auto& i : del) {
        //     cout << i.first << ": ";
        //     for (auto& j : i.second)
        //         cout << '(' << j.first << ", " << j.second << ") ";
        //     cout << endl;
        // }
        // cout << "=== TOGGLE ===\n";
        // for (auto& i : toggle) {
        //     cout << i.first << ": ";
        //     for (auto& j : i.second)
        //         cout << '(' << j.first << ", " << j.second << ") ";
        //     cout << endl;
        // }
        // cout << "=== QUERIES ===\n";
        // for (auto& i : queries) {
        //     cout << i.first << ": ";
        //     for (auto& j : i.second)
        //         cout << '(' << j.first << ", " << j.second << ") ";
        //     cout << endl;
        // }

        map<int, int> active;
        fill_n(segtree + 1, 4 * c_loc.size(), -INF);
        for (int t : c_time) {
            for (pair<int, int> i : ins[t])
                ins_ray(lower_bound(c_loc.begin(), c_loc.end(), i.first) -
                            c_loc.begin(),
                        i.second);
            for (pair<int, int> i : del[t])
                del_ray(lower_bound(c_loc.begin(), c_loc.end(), i.first) -
                            c_loc.begin(),
                        i.second);
            for (pair<int, int> i : toggle[t]) {
                active[i.first] += i.second;
                if (!active[i.first]) active.erase(i.first);
            }
            if (active.size() == k) {
                for (pair<int, int> i : queries[t]) {
                    int res = query(
                        lower_bound(c_loc.begin(), c_loc.end(), 2 * i.second) -
                        c_loc.begin());
                    if (res > 0)
                        ans[i.first] = max(ans[i.first], res - i.second);
                    // cout << "QUERY " << res << ' ' << i.second << endl;
                }
            }
        }

        for (int i = 1; i <= k; i++)
            for (auto& j : stores[i]) get<1>(j) = INF + 1 - get<1>(j);
        for (auto& i : queries)
            for (auto& j : i.second) j.second = INF + 1 - j.second;
        for (auto& i : c_loc) i = 2 * INF + 2 - i;
        reverse(c_loc.begin(), c_loc.end());
        toggle.clear(), ins.clear();
        del.clear();
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
    return 0;
}

/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/

Compilation message

new_home.cpp: In function 'void ins_ray(int, int)':
new_home.cpp:56:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     if (loc == c_loc.size()) return;
      |         ~~~~^~~~~~~~~~~~~~~
new_home.cpp: In function 'void del_ray(int, int)':
new_home.cpp:63:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if (loc == c_loc.size()) return;
      |         ~~~~^~~~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:94:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for (int i = 0; i < c_loc.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
new_home.cpp:196:31: warning: comparison of integer expressions of different signedness: 'std::map<int, int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  196 |             if (active.size() == k) {
      |                 ~~~~~~~~~~~~~~^~~~
new_home.cpp:93:14: warning: unused variable '_' [-Wunused-variable]
   93 |     for (int _ : {0, 1}) {
      |              ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21372 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21448 KB Output is correct
5 Correct 13 ms 21452 KB Output is correct
6 Correct 16 ms 21612 KB Output is correct
7 Correct 14 ms 21596 KB Output is correct
8 Correct 15 ms 21708 KB Output is correct
9 Correct 15 ms 21580 KB Output is correct
10 Correct 16 ms 21716 KB Output is correct
11 Correct 17 ms 21628 KB Output is correct
12 Correct 16 ms 21604 KB Output is correct
13 Correct 15 ms 21688 KB Output is correct
14 Correct 14 ms 21680 KB Output is correct
15 Correct 16 ms 21580 KB Output is correct
16 Correct 15 ms 21708 KB Output is correct
17 Correct 15 ms 21632 KB Output is correct
18 Correct 15 ms 21656 KB Output is correct
19 Correct 15 ms 21708 KB Output is correct
20 Correct 15 ms 21700 KB Output is correct
21 Correct 13 ms 21532 KB Output is correct
22 Correct 16 ms 21688 KB Output is correct
23 Correct 15 ms 21652 KB Output is correct
24 Correct 15 ms 21676 KB Output is correct
25 Correct 15 ms 21708 KB Output is correct
26 Correct 15 ms 21752 KB Output is correct
27 Correct 16 ms 21468 KB Output is correct
28 Correct 16 ms 21708 KB Output is correct
29 Correct 15 ms 21720 KB Output is correct
30 Correct 14 ms 21608 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21372 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21448 KB Output is correct
5 Correct 13 ms 21452 KB Output is correct
6 Correct 16 ms 21612 KB Output is correct
7 Correct 14 ms 21596 KB Output is correct
8 Correct 15 ms 21708 KB Output is correct
9 Correct 15 ms 21580 KB Output is correct
10 Correct 16 ms 21716 KB Output is correct
11 Correct 17 ms 21628 KB Output is correct
12 Correct 16 ms 21604 KB Output is correct
13 Correct 15 ms 21688 KB Output is correct
14 Correct 14 ms 21680 KB Output is correct
15 Correct 16 ms 21580 KB Output is correct
16 Correct 15 ms 21708 KB Output is correct
17 Correct 15 ms 21632 KB Output is correct
18 Correct 15 ms 21656 KB Output is correct
19 Correct 15 ms 21708 KB Output is correct
20 Correct 15 ms 21700 KB Output is correct
21 Correct 13 ms 21532 KB Output is correct
22 Correct 16 ms 21688 KB Output is correct
23 Correct 15 ms 21652 KB Output is correct
24 Correct 15 ms 21676 KB Output is correct
25 Correct 15 ms 21708 KB Output is correct
26 Correct 15 ms 21752 KB Output is correct
27 Correct 16 ms 21468 KB Output is correct
28 Correct 16 ms 21708 KB Output is correct
29 Correct 15 ms 21720 KB Output is correct
30 Correct 14 ms 21608 KB Output is correct
31 Correct 1531 ms 60420 KB Output is correct
32 Correct 84 ms 26808 KB Output is correct
33 Correct 1272 ms 59276 KB Output is correct
34 Correct 1425 ms 60016 KB Output is correct
35 Correct 1435 ms 59856 KB Output is correct
36 Correct 1428 ms 59856 KB Output is correct
37 Correct 1114 ms 58900 KB Output is correct
38 Correct 1091 ms 58476 KB Output is correct
39 Correct 856 ms 58004 KB Output is correct
40 Correct 898 ms 58092 KB Output is correct
41 Correct 1010 ms 57324 KB Output is correct
42 Correct 1042 ms 57820 KB Output is correct
43 Correct 80 ms 28740 KB Output is correct
44 Correct 1031 ms 57952 KB Output is correct
45 Correct 930 ms 57588 KB Output is correct
46 Correct 779 ms 57268 KB Output is correct
47 Correct 605 ms 56432 KB Output is correct
48 Correct 567 ms 56328 KB Output is correct
49 Correct 746 ms 56992 KB Output is correct
50 Correct 885 ms 57632 KB Output is correct
51 Correct 679 ms 56976 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4093 ms 210500 KB Output is correct
2 Correct 3447 ms 220892 KB Output is correct
3 Correct 3190 ms 217392 KB Output is correct
4 Correct 4178 ms 217268 KB Output is correct
5 Correct 3539 ms 215864 KB Output is correct
6 Correct 3397 ms 220780 KB Output is correct
7 Correct 3107 ms 217468 KB Output is correct
8 Correct 4029 ms 216684 KB Output is correct
9 Correct 4186 ms 225640 KB Output is correct
10 Correct 4030 ms 223344 KB Output is correct
11 Correct 3073 ms 220456 KB Output is correct
12 Correct 3478 ms 223188 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5068 ms 183052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21372 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21448 KB Output is correct
5 Correct 13 ms 21452 KB Output is correct
6 Correct 16 ms 21612 KB Output is correct
7 Correct 14 ms 21596 KB Output is correct
8 Correct 15 ms 21708 KB Output is correct
9 Correct 15 ms 21580 KB Output is correct
10 Correct 16 ms 21716 KB Output is correct
11 Correct 17 ms 21628 KB Output is correct
12 Correct 16 ms 21604 KB Output is correct
13 Correct 15 ms 21688 KB Output is correct
14 Correct 14 ms 21680 KB Output is correct
15 Correct 16 ms 21580 KB Output is correct
16 Correct 15 ms 21708 KB Output is correct
17 Correct 15 ms 21632 KB Output is correct
18 Correct 15 ms 21656 KB Output is correct
19 Correct 15 ms 21708 KB Output is correct
20 Correct 15 ms 21700 KB Output is correct
21 Correct 13 ms 21532 KB Output is correct
22 Correct 16 ms 21688 KB Output is correct
23 Correct 15 ms 21652 KB Output is correct
24 Correct 15 ms 21676 KB Output is correct
25 Correct 15 ms 21708 KB Output is correct
26 Correct 15 ms 21752 KB Output is correct
27 Correct 16 ms 21468 KB Output is correct
28 Correct 16 ms 21708 KB Output is correct
29 Correct 15 ms 21720 KB Output is correct
30 Correct 14 ms 21608 KB Output is correct
31 Correct 1531 ms 60420 KB Output is correct
32 Correct 84 ms 26808 KB Output is correct
33 Correct 1272 ms 59276 KB Output is correct
34 Correct 1425 ms 60016 KB Output is correct
35 Correct 1435 ms 59856 KB Output is correct
36 Correct 1428 ms 59856 KB Output is correct
37 Correct 1114 ms 58900 KB Output is correct
38 Correct 1091 ms 58476 KB Output is correct
39 Correct 856 ms 58004 KB Output is correct
40 Correct 898 ms 58092 KB Output is correct
41 Correct 1010 ms 57324 KB Output is correct
42 Correct 1042 ms 57820 KB Output is correct
43 Correct 80 ms 28740 KB Output is correct
44 Correct 1031 ms 57952 KB Output is correct
45 Correct 930 ms 57588 KB Output is correct
46 Correct 779 ms 57268 KB Output is correct
47 Correct 605 ms 56432 KB Output is correct
48 Correct 567 ms 56328 KB Output is correct
49 Correct 746 ms 56992 KB Output is correct
50 Correct 885 ms 57632 KB Output is correct
51 Correct 679 ms 56976 KB Output is correct
52 Correct 976 ms 58812 KB Output is correct
53 Correct 880 ms 57436 KB Output is correct
54 Correct 1148 ms 59080 KB Output is correct
55 Correct 915 ms 58924 KB Output is correct
56 Correct 811 ms 59640 KB Output is correct
57 Correct 957 ms 57796 KB Output is correct
58 Correct 985 ms 59000 KB Output is correct
59 Correct 971 ms 59388 KB Output is correct
60 Correct 1016 ms 57848 KB Output is correct
61 Correct 187 ms 34772 KB Output is correct
62 Correct 886 ms 59984 KB Output is correct
63 Correct 1121 ms 59196 KB Output is correct
64 Correct 1100 ms 58396 KB Output is correct
65 Correct 1273 ms 58020 KB Output is correct
66 Correct 1064 ms 57904 KB Output is correct
67 Correct 297 ms 30792 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21372 KB Output is correct
2 Correct 12 ms 21452 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21448 KB Output is correct
5 Correct 13 ms 21452 KB Output is correct
6 Correct 16 ms 21612 KB Output is correct
7 Correct 14 ms 21596 KB Output is correct
8 Correct 15 ms 21708 KB Output is correct
9 Correct 15 ms 21580 KB Output is correct
10 Correct 16 ms 21716 KB Output is correct
11 Correct 17 ms 21628 KB Output is correct
12 Correct 16 ms 21604 KB Output is correct
13 Correct 15 ms 21688 KB Output is correct
14 Correct 14 ms 21680 KB Output is correct
15 Correct 16 ms 21580 KB Output is correct
16 Correct 15 ms 21708 KB Output is correct
17 Correct 15 ms 21632 KB Output is correct
18 Correct 15 ms 21656 KB Output is correct
19 Correct 15 ms 21708 KB Output is correct
20 Correct 15 ms 21700 KB Output is correct
21 Correct 13 ms 21532 KB Output is correct
22 Correct 16 ms 21688 KB Output is correct
23 Correct 15 ms 21652 KB Output is correct
24 Correct 15 ms 21676 KB Output is correct
25 Correct 15 ms 21708 KB Output is correct
26 Correct 15 ms 21752 KB Output is correct
27 Correct 16 ms 21468 KB Output is correct
28 Correct 16 ms 21708 KB Output is correct
29 Correct 15 ms 21720 KB Output is correct
30 Correct 14 ms 21608 KB Output is correct
31 Correct 1531 ms 60420 KB Output is correct
32 Correct 84 ms 26808 KB Output is correct
33 Correct 1272 ms 59276 KB Output is correct
34 Correct 1425 ms 60016 KB Output is correct
35 Correct 1435 ms 59856 KB Output is correct
36 Correct 1428 ms 59856 KB Output is correct
37 Correct 1114 ms 58900 KB Output is correct
38 Correct 1091 ms 58476 KB Output is correct
39 Correct 856 ms 58004 KB Output is correct
40 Correct 898 ms 58092 KB Output is correct
41 Correct 1010 ms 57324 KB Output is correct
42 Correct 1042 ms 57820 KB Output is correct
43 Correct 80 ms 28740 KB Output is correct
44 Correct 1031 ms 57952 KB Output is correct
45 Correct 930 ms 57588 KB Output is correct
46 Correct 779 ms 57268 KB Output is correct
47 Correct 605 ms 56432 KB Output is correct
48 Correct 567 ms 56328 KB Output is correct
49 Correct 746 ms 56992 KB Output is correct
50 Correct 885 ms 57632 KB Output is correct
51 Correct 679 ms 56976 KB Output is correct
52 Correct 4093 ms 210500 KB Output is correct
53 Correct 3447 ms 220892 KB Output is correct
54 Correct 3190 ms 217392 KB Output is correct
55 Correct 4178 ms 217268 KB Output is correct
56 Correct 3539 ms 215864 KB Output is correct
57 Correct 3397 ms 220780 KB Output is correct
58 Correct 3107 ms 217468 KB Output is correct
59 Correct 4029 ms 216684 KB Output is correct
60 Correct 4186 ms 225640 KB Output is correct
61 Correct 4030 ms 223344 KB Output is correct
62 Correct 3073 ms 220456 KB Output is correct
63 Correct 3478 ms 223188 KB Output is correct
64 Execution timed out 5068 ms 183052 KB Time limit exceeded
65 Halted 0 ms 0 KB -