oj.uz

Submission #412654

# Submission time Handle Problem Language Result Execution time Memory
412654 2021-05-27T09:27:05 Z dolphingarlic New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 185704 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>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
typedef long long ll;
using namespace std;

const int INF = 1e8;

vector<int> c_loc, c_time;
unordered_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 -INF;
    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;
    rays[loc].insert(val);
    update(loc, *rays[loc].rbegin());
}

void del_ray(int loc, int val) {
    if (loc == c_loc.size()) return;
    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 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 t = 1; t <= k; t++) {
            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);
                if (close) {
                    active[loc]--;
                    if (!active[loc]) {
                        active.erase(loc);
                        auto ub = active.upper_bound(loc);
                        del[time].push_back({ray_at[loc], 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});
            }
        }

        unordered_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());
                    ans[i.first] = max(ans[i.first], res - i.second);
                }
            }
        }
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
    return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21452 KB Output is correct
2 Correct 16 ms 21460 KB Output is correct
3 Correct 16 ms 21436 KB Output is correct
4 Correct 14 ms 21408 KB Output is correct
5 Correct 18 ms 21472 KB Output is correct
6 Correct 18 ms 21596 KB Output is correct
7 Correct 17 ms 21576 KB Output is correct
8 Correct 17 ms 21600 KB Output is correct
9 Correct 17 ms 21588 KB Output is correct
10 Correct 19 ms 21772 KB Output is correct
11 Correct 17 ms 21580 KB Output is correct
12 Correct 18 ms 21696 KB Output is correct
13 Correct 17 ms 21600 KB Output is correct
14 Correct 16 ms 21584 KB Output is correct
15 Correct 17 ms 21580 KB Output is correct
16 Correct 18 ms 21592 KB Output is correct
17 Correct 17 ms 21580 KB Output is correct
18 Correct 18 ms 21596 KB Output is correct
19 Correct 18 ms 21592 KB Output is correct
20 Correct 18 ms 21604 KB Output is correct
21 Correct 16 ms 21480 KB Output is correct
22 Correct 16 ms 21580 KB Output is correct
23 Correct 17 ms 21692 KB Output is correct
24 Correct 17 ms 21684 KB Output is correct
25 Correct 18 ms 21600 KB Output is correct
26 Correct 16 ms 21652 KB Output is correct
27 Correct 16 ms 21452 KB Output is correct
28 Correct 16 ms 21580 KB Output is correct
29 Correct 17 ms 21596 KB Output is correct
30 Correct 19 ms 21604 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21452 KB Output is correct
2 Correct 16 ms 21460 KB Output is correct
3 Correct 16 ms 21436 KB Output is correct
4 Correct 14 ms 21408 KB Output is correct
5 Correct 18 ms 21472 KB Output is correct
6 Correct 18 ms 21596 KB Output is correct
7 Correct 17 ms 21576 KB Output is correct
8 Correct 17 ms 21600 KB Output is correct
9 Correct 17 ms 21588 KB Output is correct
10 Correct 19 ms 21772 KB Output is correct
11 Correct 17 ms 21580 KB Output is correct
12 Correct 18 ms 21696 KB Output is correct
13 Correct 17 ms 21600 KB Output is correct
14 Correct 16 ms 21584 KB Output is correct
15 Correct 17 ms 21580 KB Output is correct
16 Correct 18 ms 21592 KB Output is correct
17 Correct 17 ms 21580 KB Output is correct
18 Correct 18 ms 21596 KB Output is correct
19 Correct 18 ms 21592 KB Output is correct
20 Correct 18 ms 21604 KB Output is correct
21 Correct 16 ms 21480 KB Output is correct
22 Correct 16 ms 21580 KB Output is correct
23 Correct 17 ms 21692 KB Output is correct
24 Correct 17 ms 21684 KB Output is correct
25 Correct 18 ms 21600 KB Output is correct
26 Correct 16 ms 21652 KB Output is correct
27 Correct 16 ms 21452 KB Output is correct
28 Correct 16 ms 21580 KB Output is correct
29 Correct 17 ms 21596 KB Output is correct
30 Correct 19 ms 21604 KB Output is correct
31 Correct 1346 ms 52836 KB Output is correct
32 Correct 93 ms 26016 KB Output is correct
33 Correct 1432 ms 51204 KB Output is correct
34 Correct 1370 ms 51960 KB Output is correct
35 Correct 1433 ms 52112 KB Output is correct
36 Correct 1454 ms 52176 KB Output is correct
37 Correct 1238 ms 50988 KB Output is correct
38 Correct 1212 ms 50656 KB Output is correct
39 Correct 907 ms 50444 KB Output is correct
40 Correct 1002 ms 50460 KB Output is correct
41 Correct 1097 ms 49684 KB Output is correct
42 Correct 993 ms 50020 KB Output is correct
43 Correct 84 ms 27392 KB Output is correct
44 Correct 1000 ms 50136 KB Output is correct
45 Correct 988 ms 49900 KB Output is correct
46 Correct 927 ms 49740 KB Output is correct
47 Correct 687 ms 49200 KB Output is correct
48 Correct 676 ms 49048 KB Output is correct
49 Correct 738 ms 49576 KB Output is correct
50 Correct 776 ms 50056 KB Output is correct
51 Correct 757 ms 49440 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4180 ms 183772 KB Output is correct
2 Correct 3689 ms 176088 KB Output is correct
3 Correct 3070 ms 175340 KB Output is correct
4 Correct 4146 ms 177060 KB Output is correct
5 Correct 3668 ms 173500 KB Output is correct
6 Correct 3551 ms 176412 KB Output is correct
7 Correct 2853 ms 175168 KB Output is correct
8 Correct 4122 ms 176276 KB Output is correct
9 Correct 4297 ms 185704 KB Output is correct
10 Correct 4189 ms 182028 KB Output is correct
11 Correct 3426 ms 181576 KB Output is correct
12 Correct 3910 ms 183808 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21452 KB Output is correct
2 Correct 16 ms 21460 KB Output is correct
3 Correct 16 ms 21436 KB Output is correct
4 Correct 14 ms 21408 KB Output is correct
5 Correct 18 ms 21472 KB Output is correct
6 Correct 18 ms 21596 KB Output is correct
7 Correct 17 ms 21576 KB Output is correct
8 Correct 17 ms 21600 KB Output is correct
9 Correct 17 ms 21588 KB Output is correct
10 Correct 19 ms 21772 KB Output is correct
11 Correct 17 ms 21580 KB Output is correct
12 Correct 18 ms 21696 KB Output is correct
13 Correct 17 ms 21600 KB Output is correct
14 Correct 16 ms 21584 KB Output is correct
15 Correct 17 ms 21580 KB Output is correct
16 Correct 18 ms 21592 KB Output is correct
17 Correct 17 ms 21580 KB Output is correct
18 Correct 18 ms 21596 KB Output is correct
19 Correct 18 ms 21592 KB Output is correct
20 Correct 18 ms 21604 KB Output is correct
21 Correct 16 ms 21480 KB Output is correct
22 Correct 16 ms 21580 KB Output is correct
23 Correct 17 ms 21692 KB Output is correct
24 Correct 17 ms 21684 KB Output is correct
25 Correct 18 ms 21600 KB Output is correct
26 Correct 16 ms 21652 KB Output is correct
27 Correct 16 ms 21452 KB Output is correct
28 Correct 16 ms 21580 KB Output is correct
29 Correct 17 ms 21596 KB Output is correct
30 Correct 19 ms 21604 KB Output is correct
31 Correct 1346 ms 52836 KB Output is correct
32 Correct 93 ms 26016 KB Output is correct
33 Correct 1432 ms 51204 KB Output is correct
34 Correct 1370 ms 51960 KB Output is correct
35 Correct 1433 ms 52112 KB Output is correct
36 Correct 1454 ms 52176 KB Output is correct
37 Correct 1238 ms 50988 KB Output is correct
38 Correct 1212 ms 50656 KB Output is correct
39 Correct 907 ms 50444 KB Output is correct
40 Correct 1002 ms 50460 KB Output is correct
41 Correct 1097 ms 49684 KB Output is correct
42 Correct 993 ms 50020 KB Output is correct
43 Correct 84 ms 27392 KB Output is correct
44 Correct 1000 ms 50136 KB Output is correct
45 Correct 988 ms 49900 KB Output is correct
46 Correct 927 ms 49740 KB Output is correct
47 Correct 687 ms 49200 KB Output is correct
48 Correct 676 ms 49048 KB Output is correct
49 Correct 738 ms 49576 KB Output is correct
50 Correct 776 ms 50056 KB Output is correct
51 Correct 757 ms 49440 KB Output is correct
52 Correct 858 ms 51308 KB Output is correct
53 Correct 709 ms 49652 KB Output is correct
54 Correct 1035 ms 51392 KB Output is correct
55 Correct 807 ms 51008 KB Output is correct
56 Correct 783 ms 51828 KB Output is correct
57 Correct 951 ms 50012 KB Output is correct
58 Correct 901 ms 50856 KB Output is correct
59 Correct 888 ms 51404 KB Output is correct
60 Correct 926 ms 50280 KB Output is correct
61 Correct 146 ms 32580 KB Output is correct
62 Correct 770 ms 52228 KB Output is correct
63 Correct 931 ms 51016 KB Output is correct
64 Correct 915 ms 50492 KB Output is correct
65 Correct 1088 ms 50144 KB Output is correct
66 Correct 1063 ms 50260 KB Output is correct
67 Correct 263 ms 29896 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 21452 KB Output is correct
2 Correct 16 ms 21460 KB Output is correct
3 Correct 16 ms 21436 KB Output is correct
4 Correct 14 ms 21408 KB Output is correct
5 Correct 18 ms 21472 KB Output is correct
6 Correct 18 ms 21596 KB Output is correct
7 Correct 17 ms 21576 KB Output is correct
8 Correct 17 ms 21600 KB Output is correct
9 Correct 17 ms 21588 KB Output is correct
10 Correct 19 ms 21772 KB Output is correct
11 Correct 17 ms 21580 KB Output is correct
12 Correct 18 ms 21696 KB Output is correct
13 Correct 17 ms 21600 KB Output is correct
14 Correct 16 ms 21584 KB Output is correct
15 Correct 17 ms 21580 KB Output is correct
16 Correct 18 ms 21592 KB Output is correct
17 Correct 17 ms 21580 KB Output is correct
18 Correct 18 ms 21596 KB Output is correct
19 Correct 18 ms 21592 KB Output is correct
20 Correct 18 ms 21604 KB Output is correct
21 Correct 16 ms 21480 KB Output is correct
22 Correct 16 ms 21580 KB Output is correct
23 Correct 17 ms 21692 KB Output is correct
24 Correct 17 ms 21684 KB Output is correct
25 Correct 18 ms 21600 KB Output is correct
26 Correct 16 ms 21652 KB Output is correct
27 Correct 16 ms 21452 KB Output is correct
28 Correct 16 ms 21580 KB Output is correct
29 Correct 17 ms 21596 KB Output is correct
30 Correct 19 ms 21604 KB Output is correct
31 Correct 1346 ms 52836 KB Output is correct
32 Correct 93 ms 26016 KB Output is correct
33 Correct 1432 ms 51204 KB Output is correct
34 Correct 1370 ms 51960 KB Output is correct
35 Correct 1433 ms 52112 KB Output is correct
36 Correct 1454 ms 52176 KB Output is correct
37 Correct 1238 ms 50988 KB Output is correct
38 Correct 1212 ms 50656 KB Output is correct
39 Correct 907 ms 50444 KB Output is correct
40 Correct 1002 ms 50460 KB Output is correct
41 Correct 1097 ms 49684 KB Output is correct
42 Correct 993 ms 50020 KB Output is correct
43 Correct 84 ms 27392 KB Output is correct
44 Correct 1000 ms 50136 KB Output is correct
45 Correct 988 ms 49900 KB Output is correct
46 Correct 927 ms 49740 KB Output is correct
47 Correct 687 ms 49200 KB Output is correct
48 Correct 676 ms 49048 KB Output is correct
49 Correct 738 ms 49576 KB Output is correct
50 Correct 776 ms 50056 KB Output is correct
51 Correct 757 ms 49440 KB Output is correct
52 Correct 4180 ms 183772 KB Output is correct
53 Correct 3689 ms 176088 KB Output is correct
54 Correct 3070 ms 175340 KB Output is correct
55 Correct 4146 ms 177060 KB Output is correct
56 Correct 3668 ms 173500 KB Output is correct
57 Correct 3551 ms 176412 KB Output is correct
58 Correct 2853 ms 175168 KB Output is correct
59 Correct 4122 ms 176276 KB Output is correct
60 Correct 4297 ms 185704 KB Output is correct
61 Correct 4189 ms 182028 KB Output is correct
62 Correct 3426 ms 181576 KB Output is correct
63 Correct 3910 ms 183808 KB Output is correct
64 Execution timed out 5085 ms 156904 KB Time limit exceeded
65 Halted 0 ms 0 KB -