oj.uz

Submission #160733

# Submission time Handle Problem Language Result Execution time Memory
160733 2019-10-29T15:06:49 Z Minnakhmetov New Home (APIO18_new_home) C++14
5 / 100
 3548 ms 1048580 KB 
#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
  
using namespace std;

struct E {
    int p, t, x, y;
};

const int N = 6e5 + 5, INF = 1e9;
vector<int> vx;
multiset<int> occ[N], t[N];
int n, q, k, cc;
int ans[N];

struct ST {
    vector<int> up[N * 4];
    multiset<int> t[N];

    void push(int v, int L, int R) {
        if (!up[v].empty()) {            
            if (L != R) {
                up[v * 2].insert(up[v * 2].end(), all(up[v]));
                up[v * 2 + 1].insert(up[v * 2 + 1].end(), all(up[v]));
            }
            else {
                for (int x : up[v]) {
                    if (x < 0) {
                        if (!t[L].count(-x))
                            continue;
                        t[L].erase(t[L].find(-x));
                    }
                    else {
                        t[L].insert(x);
                    }
                }    
            }
            up[v].clear();
        }
    }

    void upd(int l, int r, int x, int v, int L, int R) {
        push(v, L, R);
        if (l > r)
            return;
        if (l == L && r == R) {
            up[v].push_back(x);
        }
        else {
            int m = (L + R) >> 1;
            upd(l, min(m, r), x, v * 2, L, m);
            upd(max(m + 1, l), r, x, v * 2 + 1, m + 1, R);
        }
    }
} segt[2];

int que(int x, int v, int L, int R, ST &a, ST &b) {
    a.push(v, L, R);
    b.push(v, L, R);

    if (L == R) {
        if (a.t[L].size() + b.t[L].size() < k)
            return -1;

        int ans = 0;
        if (!a.t[L].empty())
            ans = max(ans, vx[L] - *a.t[L].begin());
        if (!b.t[L].empty())
            ans = max(ans, *b.t[L].rbegin() - vx[L]);

        return ans;
    }
    int m = (L + R) >> 1;
    if (x <= m)
        return que(x, v * 2, L, m, a, b);
    return que(x, v * 2 + 1, m + 1, R, a, b);
}

void updBetween(int x, int y, int k) {
    if (x == y)
        return;

    // cout << "BET " << x << " " << y << " " << k << "\n";

    int m = (x + y) / 2,
        m1 = upper_bound(all(vx), m) - vx.begin(),
        x1 = lower_bound(all(vx), x) - vx.begin(),
        y1 = lower_bound(all(vx), y) - vx.begin();

    segt[0].upd(x1, m1 - 1, k * x, 1, 0, cc - 1);
    segt[1].upd(m1, y1 - 1, k * y, 1, 0, cc - 1);
}

void updBegin(int x, int k) {
    // cout << "BEG " << x << " " << k << "\n";
    // return;

    int x1 = lower_bound(all(vx), x) - vx.begin();
    segt[1].upd(0, x1 - 1, x * k, 1, 0, cc - 1);
}

void updEnd(int x, int k) {
    // cout << "END " << x << " " << k << "\n";

    int x1 = lower_bound(all(vx), x) - vx.begin();
    segt[0].upd(x1, cc - 1, x * k, 1, 0, cc - 1);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> k >> q;

    vector<E> evs;

    for (int i = 0; i < n; i++) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        t--;
        evs.push_back({a, 0, x, t});
        evs.push_back({b + 1, 1, x, t});
        vx.push_back(x);
    }

    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        evs.push_back({y, 2, x, i});
        vx.push_back(x);
    }

    sort(all(vx));
    vx.erase(unique(all(vx)), vx.end());

    cc = vx.size();

    sort(all(evs), [](const E &lt, const E &rt) {
        return lt.p == rt.p ? lt.t < rt.t : lt.p < rt.p;
    });

    for (E e : evs) {
        // cout << e.p << " " << e.t << " " << e.x << " " << e.y << "\n";
        if (e.t == 0) {
            if (!occ[e.y].empty()) {
                auto it = occ[e.y].upper_bound(e.x);

                if (it == occ[e.y].begin()) {
                    updBegin(*occ[e.y].begin(), -1);
                }
                else if (it == occ[e.y].end()) {
                    updEnd(*occ[e.y].rbegin(), -1);
                }
                else {
                    updBetween(*prev(it), *it, -1);
                }
            }

            auto it = occ[e.y].insert(e.x);

            if (it == occ[e.y].begin())
                updBegin(*it, 1);
            else
                updBetween(*prev(it), *it, 1);

            if (next(it) == occ[e.y].end())
                updEnd(*it, 1);
            else
                updBetween(*it, *next(it), 1);
        }
        else if (e.t == 1) {
            auto it = occ[e.y].lower_bound(e.x);

            if (it == occ[e.y].begin())
                updBegin(*it, -1);
            else
                updBetween(*prev(it), *it, -1);

            if (next(it) == occ[e.y].end())
                updEnd(*it, -1);
            else
                updBetween(*it, *next(it), -1);

            it++;
            occ[e.y].erase(prev(it));

            if (!occ[e.y].empty()) {
                if (it == occ[e.y].begin()) {
                    updBegin(*occ[e.y].begin(), 1);
                }
                else if (it == occ[e.y].end()) {
                    updEnd(*occ[e.y].rbegin(), 1);
                }
                else {
                    updBetween(*prev(it), *it, 1);
                }
            }
        }
        else {
            e.x = lower_bound(all(vx), e.x) - vx.begin();
            ans[e.y] = que(e.x, 1, 0, cc - 1, segt[0], segt[1]);
        }
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}

Compilation message

new_home.cpp: In function 'int que(int, int, int, int, ST&, ST&)':
new_home.cpp:64:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (a.t[L].size() + b.t[L].size() < k)
             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 225840 KB Output is correct
2 Correct 208 ms 225760 KB Output is correct
3 Correct 207 ms 225720 KB Output is correct
4 Correct 208 ms 225784 KB Output is correct
5 Correct 267 ms 225888 KB Output is correct
6 Correct 232 ms 227192 KB Output is correct
7 Correct 337 ms 232312 KB Output is correct
8 Correct 315 ms 232056 KB Output is correct
9 Correct 302 ms 236540 KB Output is correct
10 Correct 231 ms 227020 KB Output is correct
11 Correct 247 ms 229624 KB Output is correct
12 Correct 223 ms 227276 KB Output is correct
13 Correct 232 ms 229612 KB Output is correct
14 Correct 301 ms 228988 KB Output is correct
15 Correct 289 ms 233884 KB Output is correct
16 Correct 290 ms 235896 KB Output is correct
17 Correct 292 ms 231132 KB Output is correct
18 Correct 321 ms 234104 KB Output is correct
19 Correct 299 ms 235640 KB Output is correct
20 Correct 285 ms 231032 KB Output is correct
21 Correct 231 ms 226168 KB Output is correct
22 Correct 311 ms 237432 KB Output is correct
23 Correct 319 ms 235152 KB Output is correct
24 Correct 309 ms 233116 KB Output is correct
25 Correct 283 ms 230336 KB Output is correct
26 Correct 246 ms 229496 KB Output is correct
27 Correct 226 ms 225896 KB Output is correct
28 Correct 243 ms 229240 KB Output is correct
29 Correct 233 ms 229112 KB Output is correct
30 Correct 228 ms 228508 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 225840 KB Output is correct
2 Correct 208 ms 225760 KB Output is correct
3 Correct 207 ms 225720 KB Output is correct
4 Correct 208 ms 225784 KB Output is correct
5 Correct 267 ms 225888 KB Output is correct
6 Correct 232 ms 227192 KB Output is correct
7 Correct 337 ms 232312 KB Output is correct
8 Correct 315 ms 232056 KB Output is correct
9 Correct 302 ms 236540 KB Output is correct
10 Correct 231 ms 227020 KB Output is correct
11 Correct 247 ms 229624 KB Output is correct
12 Correct 223 ms 227276 KB Output is correct
13 Correct 232 ms 229612 KB Output is correct
14 Correct 301 ms 228988 KB Output is correct
15 Correct 289 ms 233884 KB Output is correct
16 Correct 290 ms 235896 KB Output is correct
17 Correct 292 ms 231132 KB Output is correct
18 Correct 321 ms 234104 KB Output is correct
19 Correct 299 ms 235640 KB Output is correct
20 Correct 285 ms 231032 KB Output is correct
21 Correct 231 ms 226168 KB Output is correct
22 Correct 311 ms 237432 KB Output is correct
23 Correct 319 ms 235152 KB Output is correct
24 Correct 309 ms 233116 KB Output is correct
25 Correct 283 ms 230336 KB Output is correct
26 Correct 246 ms 229496 KB Output is correct
27 Correct 226 ms 225896 KB Output is correct
28 Correct 243 ms 229240 KB Output is correct
29 Correct 233 ms 229112 KB Output is correct
30 Correct 228 ms 228508 KB Output is correct
31 Runtime error 3548 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2153 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 2230 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 225840 KB Output is correct
2 Correct 208 ms 225760 KB Output is correct
3 Correct 207 ms 225720 KB Output is correct
4 Correct 208 ms 225784 KB Output is correct
5 Correct 267 ms 225888 KB Output is correct
6 Correct 232 ms 227192 KB Output is correct
7 Correct 337 ms 232312 KB Output is correct
8 Correct 315 ms 232056 KB Output is correct
9 Correct 302 ms 236540 KB Output is correct
10 Correct 231 ms 227020 KB Output is correct
11 Correct 247 ms 229624 KB Output is correct
12 Correct 223 ms 227276 KB Output is correct
13 Correct 232 ms 229612 KB Output is correct
14 Correct 301 ms 228988 KB Output is correct
15 Correct 289 ms 233884 KB Output is correct
16 Correct 290 ms 235896 KB Output is correct
17 Correct 292 ms 231132 KB Output is correct
18 Correct 321 ms 234104 KB Output is correct
19 Correct 299 ms 235640 KB Output is correct
20 Correct 285 ms 231032 KB Output is correct
21 Correct 231 ms 226168 KB Output is correct
22 Correct 311 ms 237432 KB Output is correct
23 Correct 319 ms 235152 KB Output is correct
24 Correct 309 ms 233116 KB Output is correct
25 Correct 283 ms 230336 KB Output is correct
26 Correct 246 ms 229496 KB Output is correct
27 Correct 226 ms 225896 KB Output is correct
28 Correct 243 ms 229240 KB Output is correct
29 Correct 233 ms 229112 KB Output is correct
30 Correct 228 ms 228508 KB Output is correct
31 Runtime error 3548 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 225840 KB Output is correct
2 Correct 208 ms 225760 KB Output is correct
3 Correct 207 ms 225720 KB Output is correct
4 Correct 208 ms 225784 KB Output is correct
5 Correct 267 ms 225888 KB Output is correct
6 Correct 232 ms 227192 KB Output is correct
7 Correct 337 ms 232312 KB Output is correct
8 Correct 315 ms 232056 KB Output is correct
9 Correct 302 ms 236540 KB Output is correct
10 Correct 231 ms 227020 KB Output is correct
11 Correct 247 ms 229624 KB Output is correct
12 Correct 223 ms 227276 KB Output is correct
13 Correct 232 ms 229612 KB Output is correct
14 Correct 301 ms 228988 KB Output is correct
15 Correct 289 ms 233884 KB Output is correct
16 Correct 290 ms 235896 KB Output is correct
17 Correct 292 ms 231132 KB Output is correct
18 Correct 321 ms 234104 KB Output is correct
19 Correct 299 ms 235640 KB Output is correct
20 Correct 285 ms 231032 KB Output is correct
21 Correct 231 ms 226168 KB Output is correct
22 Correct 311 ms 237432 KB Output is correct
23 Correct 319 ms 235152 KB Output is correct
24 Correct 309 ms 233116 KB Output is correct
25 Correct 283 ms 230336 KB Output is correct
26 Correct 246 ms 229496 KB Output is correct
27 Correct 226 ms 225896 KB Output is correct
28 Correct 243 ms 229240 KB Output is correct
29 Correct 233 ms 229112 KB Output is correct
30 Correct 228 ms 228508 KB Output is correct
31 Runtime error 3548 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -