oj.uz

Submission #412619

# Submission time Handle Problem Language Result Execution time Memory
412619 2021-05-27T08:00:59 Z dolphingarlic New Home (APIO18_new_home) C++14
0 / 100
 5000 ms 224196 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);

    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21372 KB Output is correct
2 Correct 12 ms 21456 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21460 KB Output is correct
5 Correct 15 ms 21532 KB Output is correct
6 Correct 17 ms 21672 KB Output is correct
7 Correct 14 ms 21708 KB Output is correct
8 Correct 15 ms 21660 KB Output is correct
9 Correct 14 ms 21708 KB Output is correct
10 Correct 16 ms 21728 KB Output is correct
11 Correct 15 ms 21608 KB Output is correct
12 Correct 17 ms 21708 KB Output is correct
13 Correct 17 ms 21668 KB Output is correct
14 Correct 15 ms 21708 KB Output is correct
15 Correct 18 ms 21708 KB Output is correct
16 Correct 14 ms 21736 KB Output is correct
17 Correct 15 ms 21732 KB Output is correct
18 Correct 15 ms 21732 KB Output is correct
19 Correct 15 ms 21708 KB Output is correct
20 Correct 15 ms 21708 KB Output is correct
21 Incorrect 14 ms 21452 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21372 KB Output is correct
2 Correct 12 ms 21456 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21460 KB Output is correct
5 Correct 15 ms 21532 KB Output is correct
6 Correct 17 ms 21672 KB Output is correct
7 Correct 14 ms 21708 KB Output is correct
8 Correct 15 ms 21660 KB Output is correct
9 Correct 14 ms 21708 KB Output is correct
10 Correct 16 ms 21728 KB Output is correct
11 Correct 15 ms 21608 KB Output is correct
12 Correct 17 ms 21708 KB Output is correct
13 Correct 17 ms 21668 KB Output is correct
14 Correct 15 ms 21708 KB Output is correct
15 Correct 18 ms 21708 KB Output is correct
16 Correct 14 ms 21736 KB Output is correct
17 Correct 15 ms 21732 KB Output is correct
18 Correct 15 ms 21732 KB Output is correct
19 Correct 15 ms 21708 KB Output is correct
20 Correct 15 ms 21708 KB Output is correct
21 Incorrect 14 ms 21452 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21372 KB Output is correct
2 Correct 12 ms 21456 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21460 KB Output is correct
5 Correct 15 ms 21532 KB Output is correct
6 Correct 17 ms 21672 KB Output is correct
7 Correct 14 ms 21708 KB Output is correct
8 Correct 15 ms 21660 KB Output is correct
9 Correct 14 ms 21708 KB Output is correct
10 Correct 16 ms 21728 KB Output is correct
11 Correct 15 ms 21608 KB Output is correct
12 Correct 17 ms 21708 KB Output is correct
13 Correct 17 ms 21668 KB Output is correct
14 Correct 15 ms 21708 KB Output is correct
15 Correct 18 ms 21708 KB Output is correct
16 Correct 14 ms 21736 KB Output is correct
17 Correct 15 ms 21732 KB Output is correct
18 Correct 15 ms 21732 KB Output is correct
19 Correct 15 ms 21708 KB Output is correct
20 Correct 15 ms 21708 KB Output is correct
21 Incorrect 14 ms 21452 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21372 KB Output is correct
2 Correct 12 ms 21456 KB Output is correct
3 Correct 12 ms 21452 KB Output is correct
4 Correct 12 ms 21460 KB Output is correct
5 Correct 15 ms 21532 KB Output is correct
6 Correct 17 ms 21672 KB Output is correct
7 Correct 14 ms 21708 KB Output is correct
8 Correct 15 ms 21660 KB Output is correct
9 Correct 14 ms 21708 KB Output is correct
10 Correct 16 ms 21728 KB Output is correct
11 Correct 15 ms 21608 KB Output is correct
12 Correct 17 ms 21708 KB Output is correct
13 Correct 17 ms 21668 KB Output is correct
14 Correct 15 ms 21708 KB Output is correct
15 Correct 18 ms 21708 KB Output is correct
16 Correct 14 ms 21736 KB Output is correct
17 Correct 15 ms 21732 KB Output is correct
18 Correct 15 ms 21732 KB Output is correct
19 Correct 15 ms 21708 KB Output is correct
20 Correct 15 ms 21708 KB Output is correct
21 Incorrect 14 ms 21452 KB Output isn't correct
22 Halted 0 ms 0 KB -