oj.uz

Submission #988460

# Submission time Handle Problem Language Result Execution time Memory
988460 2024-05-24T18:03:01 Z 876pol New Home (APIO18_new_home) C++17
5 / 100
 3124 ms 1041052 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 = 1e7;
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 60 ms 157016 KB Output is correct
2 Correct 61 ms 157016 KB Output is correct
3 Correct 61 ms 156860 KB Output is correct
4 Correct 56 ms 157012 KB Output is correct
5 Correct 65 ms 156940 KB Output is correct
6 Correct 69 ms 161624 KB Output is correct
7 Correct 63 ms 159572 KB Output is correct
8 Correct 64 ms 158860 KB Output is correct
9 Correct 68 ms 158804 KB Output is correct
10 Correct 67 ms 160336 KB Output is correct
11 Correct 64 ms 159216 KB Output is correct
12 Correct 73 ms 162132 KB Output is correct
13 Correct 70 ms 159572 KB Output is correct
14 Correct 67 ms 160852 KB Output is correct
15 Correct 70 ms 159920 KB Output is correct
16 Correct 69 ms 159572 KB Output is correct
17 Correct 68 ms 160592 KB Output is correct
18 Correct 67 ms 159572 KB Output is correct
19 Correct 76 ms 159816 KB Output is correct
20 Correct 73 ms 159840 KB Output is correct
21 Correct 62 ms 157008 KB Output is correct
22 Correct 65 ms 158544 KB Output is correct
23 Correct 67 ms 159060 KB Output is correct
24 Correct 66 ms 159336 KB Output is correct
25 Correct 67 ms 159828 KB Output is correct
26 Correct 72 ms 161704 KB Output is correct
27 Correct 70 ms 157008 KB Output is correct
28 Correct 71 ms 160732 KB Output is correct
29 Correct 66 ms 160856 KB Output is correct
30 Correct 70 ms 160852 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 157016 KB Output is correct
2 Correct 61 ms 157016 KB Output is correct
3 Correct 61 ms 156860 KB Output is correct
4 Correct 56 ms 157012 KB Output is correct
5 Correct 65 ms 156940 KB Output is correct
6 Correct 69 ms 161624 KB Output is correct
7 Correct 63 ms 159572 KB Output is correct
8 Correct 64 ms 158860 KB Output is correct
9 Correct 68 ms 158804 KB Output is correct
10 Correct 67 ms 160336 KB Output is correct
11 Correct 64 ms 159216 KB Output is correct
12 Correct 73 ms 162132 KB Output is correct
13 Correct 70 ms 159572 KB Output is correct
14 Correct 67 ms 160852 KB Output is correct
15 Correct 70 ms 159920 KB Output is correct
16 Correct 69 ms 159572 KB Output is correct
17 Correct 68 ms 160592 KB Output is correct
18 Correct 67 ms 159572 KB Output is correct
19 Correct 76 ms 159816 KB Output is correct
20 Correct 73 ms 159840 KB Output is correct
21 Correct 62 ms 157008 KB Output is correct
22 Correct 65 ms 158544 KB Output is correct
23 Correct 67 ms 159060 KB Output is correct
24 Correct 66 ms 159336 KB Output is correct
25 Correct 67 ms 159828 KB Output is correct
26 Correct 72 ms 161704 KB Output is correct
27 Correct 70 ms 157008 KB Output is correct
28 Correct 71 ms 160732 KB Output is correct
29 Correct 66 ms 160856 KB Output is correct
30 Correct 70 ms 160852 KB Output is correct
31 Runtime error 1290 ms 675472 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2387 ms 1028412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 3124 ms 1041052 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 157016 KB Output is correct
2 Correct 61 ms 157016 KB Output is correct
3 Correct 61 ms 156860 KB Output is correct
4 Correct 56 ms 157012 KB Output is correct
5 Correct 65 ms 156940 KB Output is correct
6 Correct 69 ms 161624 KB Output is correct
7 Correct 63 ms 159572 KB Output is correct
8 Correct 64 ms 158860 KB Output is correct
9 Correct 68 ms 158804 KB Output is correct
10 Correct 67 ms 160336 KB Output is correct
11 Correct 64 ms 159216 KB Output is correct
12 Correct 73 ms 162132 KB Output is correct
13 Correct 70 ms 159572 KB Output is correct
14 Correct 67 ms 160852 KB Output is correct
15 Correct 70 ms 159920 KB Output is correct
16 Correct 69 ms 159572 KB Output is correct
17 Correct 68 ms 160592 KB Output is correct
18 Correct 67 ms 159572 KB Output is correct
19 Correct 76 ms 159816 KB Output is correct
20 Correct 73 ms 159840 KB Output is correct
21 Correct 62 ms 157008 KB Output is correct
22 Correct 65 ms 158544 KB Output is correct
23 Correct 67 ms 159060 KB Output is correct
24 Correct 66 ms 159336 KB Output is correct
25 Correct 67 ms 159828 KB Output is correct
26 Correct 72 ms 161704 KB Output is correct
27 Correct 70 ms 157008 KB Output is correct
28 Correct 71 ms 160732 KB Output is correct
29 Correct 66 ms 160856 KB Output is correct
30 Correct 70 ms 160852 KB Output is correct
31 Runtime error 1290 ms 675472 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 157016 KB Output is correct
2 Correct 61 ms 157016 KB Output is correct
3 Correct 61 ms 156860 KB Output is correct
4 Correct 56 ms 157012 KB Output is correct
5 Correct 65 ms 156940 KB Output is correct
6 Correct 69 ms 161624 KB Output is correct
7 Correct 63 ms 159572 KB Output is correct
8 Correct 64 ms 158860 KB Output is correct
9 Correct 68 ms 158804 KB Output is correct
10 Correct 67 ms 160336 KB Output is correct
11 Correct 64 ms 159216 KB Output is correct
12 Correct 73 ms 162132 KB Output is correct
13 Correct 70 ms 159572 KB Output is correct
14 Correct 67 ms 160852 KB Output is correct
15 Correct 70 ms 159920 KB Output is correct
16 Correct 69 ms 159572 KB Output is correct
17 Correct 68 ms 160592 KB Output is correct
18 Correct 67 ms 159572 KB Output is correct
19 Correct 76 ms 159816 KB Output is correct
20 Correct 73 ms 159840 KB Output is correct
21 Correct 62 ms 157008 KB Output is correct
22 Correct 65 ms 158544 KB Output is correct
23 Correct 67 ms 159060 KB Output is correct
24 Correct 66 ms 159336 KB Output is correct
25 Correct 67 ms 159828 KB Output is correct
26 Correct 72 ms 161704 KB Output is correct
27 Correct 70 ms 157008 KB Output is correct
28 Correct 71 ms 160732 KB Output is correct
29 Correct 66 ms 160856 KB Output is correct
30 Correct 70 ms 160852 KB Output is correct
31 Runtime error 1290 ms 675472 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -