oj.uz

Submission #988461

# Submission time Handle Problem Language Result Execution time Memory
988461 2024-05-24T18:04:26 Z 876pol New Home (APIO18_new_home) C++17
5 / 100
 4808 ms 1048576 KB 
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= e; i++)
#define TRAV(e, a) for (const auto &e : a)
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl;

template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &out, const T &obj) {
    out << "[";
    for (auto it = obj.begin(); it != obj.end(); it++) {
        out << &", "[2 * (it == obj.begin())] << *it;
    }
    return out << "]";
}

template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
    return out << "(" << obj.first << ", " << obj.second << ")";
}

struct query {
    ll op, x, t, y, id;
};

ostream &operator<<(ostream &out, const query &obj) {
    return out << vec<ll>{obj.op, obj.x, obj.t, obj.y, obj.id};
}

const ll MXL = 2e7;
const ll SZ = 450, NB = 800;
bitset<SZ> dat[MXL];
ll lc[MXL], rc[MXL], roots[NB];
ll curr = NB;

void push(ll v, ll tl, ll tr) {
    if (tl == tr) return;
    if (lc[v] == -1) lc[v] = curr++;
    if (rc[v] == -1) rc[v] = curr++;
}

void toggle(ll v, ll tl, ll tr, ll ind, ll t) {
    push(v, tl, tr);
    if (tl == tr) {
        dat[v][t] = !dat[v][t];
    } else {
        ll tm = (tl + tr) / 2;
        if (ind <= tm) {
            toggle(lc[v], tl, tm, ind, t);
        } else {
            toggle(rc[v], tm + 1, tr, ind, t);
        }
        dat[v] = dat[lc[v]] | dat[rc[v]];
    }
}

bitset<SZ> qu(ll v, ll tl, ll tr, ll l, ll r) {
    push(v, tl, tr);
    if (r < tl || tr < l) return bitset<SZ>();
    if (l <= tl && tr <= r) return dat[v];
    ll tm = (tl + tr) / 2;
    return qu(lc[v], tl, tm, l, r) | qu(rc[v], tm + 1, tr, l, r);
}

int main() {
    memset(lc, -1, sizeof(lc));
    memset(rc, -1, sizeof(rc));
    FOR(i, 0, NB) roots[i] = i;
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n, k, q;
    cin >> n >> k >> q;
    vec<query> queries;
    queries.reserve(2 * n + q);
    FOR(i, 0, n) {
        ll x, t, a, b;
        cin >> x >> t >> a >> b;
        queries.push_back({0, x, t, a, i});
        queries.push_back({1, x, t, b + 1, i});
    }
    FOR(i, 0, q) {
        ll l, y;
        cin >> l >> y;
        queries.push_back({2, l, -1, y, i});
    }
    sort(all(queries), [&](const query &o1, const query &o2) {
        return (o1.y == o2.y) ? o1.op < o2.op : o1.y < o2.y;
    });
    map<pll, ll> cnt;
    vec<ll> ans(q);
    TRAV(e, queries) {
        if (e.op == 0) {
            if (cnt[{e.x, e.t}]++ == 0) {
                toggle(0, 1, 1e8, e.x, e.t);
            }
        } else if (e.op == 1) {
            if (--cnt[{e.x, e.t}] == 0) {
                toggle(0, 1, 1e8, e.x, e.t);
            }
        } else if (e.op == 2) {
            ll l = 0, r = 1e8, best = -1;
            while (l <= r) {
                ll m = (l + r) / 2;
                if (qu(0, 1, 1e8, e.x - m, e.x + m).count() == k) {
                    best = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            ans[e.id] = best;
        }
    }
    TRAV(e, ans) cout << e << "\n";
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:121:61: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  121 |                 if (qu(0, 1, 1e8, e.x - m, e.x + m).count() == k) {
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 314572 KB Output is correct
2 Correct 125 ms 314508 KB Output is correct
3 Correct 109 ms 314448 KB Output is correct
4 Correct 120 ms 314592 KB Output is correct
5 Correct 129 ms 314428 KB Output is correct
6 Correct 137 ms 318568 KB Output is correct
7 Correct 113 ms 316240 KB Output is correct
8 Correct 132 ms 315572 KB Output is correct
9 Correct 135 ms 315840 KB Output is correct
10 Correct 129 ms 317268 KB Output is correct
11 Correct 124 ms 316120 KB Output is correct
12 Correct 133 ms 319056 KB Output is correct
13 Correct 124 ms 316120 KB Output is correct
14 Correct 118 ms 317992 KB Output is correct
15 Correct 129 ms 316700 KB Output is correct
16 Correct 129 ms 316500 KB Output is correct
17 Correct 130 ms 317472 KB Output is correct
18 Correct 126 ms 316388 KB Output is correct
19 Correct 125 ms 315984 KB Output is correct
20 Correct 127 ms 316540 KB Output is correct
21 Correct 127 ms 314472 KB Output is correct
22 Correct 116 ms 315364 KB Output is correct
23 Correct 122 ms 315740 KB Output is correct
24 Correct 127 ms 316024 KB Output is correct
25 Correct 115 ms 316756 KB Output is correct
26 Correct 134 ms 318804 KB Output is correct
27 Correct 130 ms 314480 KB Output is correct
28 Correct 128 ms 317860 KB Output is correct
29 Correct 127 ms 318036 KB Output is correct
30 Correct 122 ms 318064 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 314572 KB Output is correct
2 Correct 125 ms 314508 KB Output is correct
3 Correct 109 ms 314448 KB Output is correct
4 Correct 120 ms 314592 KB Output is correct
5 Correct 129 ms 314428 KB Output is correct
6 Correct 137 ms 318568 KB Output is correct
7 Correct 113 ms 316240 KB Output is correct
8 Correct 132 ms 315572 KB Output is correct
9 Correct 135 ms 315840 KB Output is correct
10 Correct 129 ms 317268 KB Output is correct
11 Correct 124 ms 316120 KB Output is correct
12 Correct 133 ms 319056 KB Output is correct
13 Correct 124 ms 316120 KB Output is correct
14 Correct 118 ms 317992 KB Output is correct
15 Correct 129 ms 316700 KB Output is correct
16 Correct 129 ms 316500 KB Output is correct
17 Correct 130 ms 317472 KB Output is correct
18 Correct 126 ms 316388 KB Output is correct
19 Correct 125 ms 315984 KB Output is correct
20 Correct 127 ms 316540 KB Output is correct
21 Correct 127 ms 314472 KB Output is correct
22 Correct 116 ms 315364 KB Output is correct
23 Correct 122 ms 315740 KB Output is correct
24 Correct 127 ms 316024 KB Output is correct
25 Correct 115 ms 316756 KB Output is correct
26 Correct 134 ms 318804 KB Output is correct
27 Correct 130 ms 314480 KB Output is correct
28 Correct 128 ms 317860 KB Output is correct
29 Correct 127 ms 318036 KB Output is correct
30 Correct 122 ms 318064 KB Output is correct
31 Runtime error 4808 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 314572 KB Output is correct
2 Correct 125 ms 314508 KB Output is correct
3 Correct 109 ms 314448 KB Output is correct
4 Correct 120 ms 314592 KB Output is correct
5 Correct 129 ms 314428 KB Output is correct
6 Correct 137 ms 318568 KB Output is correct
7 Correct 113 ms 316240 KB Output is correct
8 Correct 132 ms 315572 KB Output is correct
9 Correct 135 ms 315840 KB Output is correct
10 Correct 129 ms 317268 KB Output is correct
11 Correct 124 ms 316120 KB Output is correct
12 Correct 133 ms 319056 KB Output is correct
13 Correct 124 ms 316120 KB Output is correct
14 Correct 118 ms 317992 KB Output is correct
15 Correct 129 ms 316700 KB Output is correct
16 Correct 129 ms 316500 KB Output is correct
17 Correct 130 ms 317472 KB Output is correct
18 Correct 126 ms 316388 KB Output is correct
19 Correct 125 ms 315984 KB Output is correct
20 Correct 127 ms 316540 KB Output is correct
21 Correct 127 ms 314472 KB Output is correct
22 Correct 116 ms 315364 KB Output is correct
23 Correct 122 ms 315740 KB Output is correct
24 Correct 127 ms 316024 KB Output is correct
25 Correct 115 ms 316756 KB Output is correct
26 Correct 134 ms 318804 KB Output is correct
27 Correct 130 ms 314480 KB Output is correct
28 Correct 128 ms 317860 KB Output is correct
29 Correct 127 ms 318036 KB Output is correct
30 Correct 122 ms 318064 KB Output is correct
31 Runtime error 4808 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 314572 KB Output is correct
2 Correct 125 ms 314508 KB Output is correct
3 Correct 109 ms 314448 KB Output is correct
4 Correct 120 ms 314592 KB Output is correct
5 Correct 129 ms 314428 KB Output is correct
6 Correct 137 ms 318568 KB Output is correct
7 Correct 113 ms 316240 KB Output is correct
8 Correct 132 ms 315572 KB Output is correct
9 Correct 135 ms 315840 KB Output is correct
10 Correct 129 ms 317268 KB Output is correct
11 Correct 124 ms 316120 KB Output is correct
12 Correct 133 ms 319056 KB Output is correct
13 Correct 124 ms 316120 KB Output is correct
14 Correct 118 ms 317992 KB Output is correct
15 Correct 129 ms 316700 KB Output is correct
16 Correct 129 ms 316500 KB Output is correct
17 Correct 130 ms 317472 KB Output is correct
18 Correct 126 ms 316388 KB Output is correct
19 Correct 125 ms 315984 KB Output is correct
20 Correct 127 ms 316540 KB Output is correct
21 Correct 127 ms 314472 KB Output is correct
22 Correct 116 ms 315364 KB Output is correct
23 Correct 122 ms 315740 KB Output is correct
24 Correct 127 ms 316024 KB Output is correct
25 Correct 115 ms 316756 KB Output is correct
26 Correct 134 ms 318804 KB Output is correct
27 Correct 130 ms 314480 KB Output is correct
28 Correct 128 ms 317860 KB Output is correct
29 Correct 127 ms 318036 KB Output is correct
30 Correct 122 ms 318064 KB Output is correct
31 Runtime error 4808 ms 1048576 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -