Submission #988460

#	Time	Username	Problem	Language	Result	Execution time	Memory
988460		876pol	New Home (APIO18_new_home)	C++17	5 / 100	3124 ms	1041052 KiB

new_home

#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 (stderr)

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 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20