p394.ans1
======================
2
1 2

=================
p394.ans2
======================
0

=================
p394.ans3
======================
1
2

=================
p394.cpp
======================
#include <bits/stdc++.h>
// #include <coding_library/data_structures/fenwick.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class T>
class Fenwick {
  private:
    int sz, log_size;
    vector<T> tr;

  public:
    void init(int n) {
        sz = n + 1;
        log_size = 31 - __builtin_clz(sz);
        tr.assign(sz + 1, 0);
    }

    void update(int idx, T val) {
        if(idx <= 0) {
            assert(false);
            return;
        }
        for(; idx <= sz; idx += (idx & -idx)) {
            tr[idx] += val;
        }
    }

    T query(int idx) {
        T ans = 0;
        for(; idx >= 1; idx -= (idx & -idx)) {
            ans += tr[idx];
        }

        return ans;
    }

    T query(int l, int r) { return query(r) - query(l - 1); }

    int find_kth(T k) {
        int idx = 0;
        for(int i = log_size; i >= 0; i--) {
            if(idx + (1 << i) < sz && tr[idx + (1 << i)] < k) {
                k -= tr[idx + (1 << i)];
                idx += (1 << i);
            }
        }
        return idx + 1;
    }
};

int n, k;
vector<int64_t> x, y, w;

void read() {
    cin >> n >> k;
    x.resize(n);
    y.resize(n);
    w.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> w[i];
    }
}

void solve() {
    // We will start with the standard trick of rotating everything by 45%
    // degrees and scaling by two with (x, y) goes into (x + y, x - y). The area
    // of each pizza hut is now a rectangle with corners (x - w, y - w) and (x +
    // w, y + w), where this is the transformed (x, y). We want to figure out
    // which centers are covered by at least K rectangles (excluding the given
    // one). This can be done by treating each rectangle as two events (low_y,
    // high_y, low_x, +1), and (low_y, high_y, high_x, -1), and maintaining a
    // segment or fenwick tree over the Ys. We will add +delta at low_y and
    // subtract it at (high_y+1). Then we will also have each center as a query,
    // and we can simply query the fenwick tree. For convenince, we can compress
    // all Y coordinates before processing the events.

    vector<int64_t> tx(n), ty(n);
    for(int i = 0; i < n; i++) {
        tx[i] = x[i] + y[i];
        ty[i] = x[i] - y[i];
    }

    vector<int64_t> all_ys;
    for(int i = 0; i < n; i++) {
        all_ys.push_back(ty[i] - w[i]);
        all_ys.push_back(ty[i] + w[i] + 1);
        all_ys.push_back(ty[i]);
    }
    sort(all_ys.begin(), all_ys.end());
    all_ys.erase(unique(all_ys.begin(), all_ys.end()), all_ys.end());

    auto compress = [&](int64_t v) -> int {
        return lower_bound(all_ys.begin(), all_ys.end(), v) - all_ys.begin() +
               1;
    };

    struct Event {
        int64_t x_coord;
        int type;
        int idx;
        int delta;
    };

    vector<Event> events;
    for(int i = 0; i < n; i++) {
        events.push_back({tx[i] - w[i], 0, i, 1});
        events.push_back({tx[i] + w[i] + 1, 0, i, -1});
        events.push_back({tx[i], 1, i, 0});
    }

    sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
        if(a.x_coord != b.x_coord) {
            return a.x_coord < b.x_coord;
        }
        return a.type < b.type;
    });

    Fenwick<int> fw;
    fw.init(all_ys.size());

    vector<int> cnt(n);
    for(auto& e: events) {
        if(e.type == 0) {
            int lo = compress(ty[e.idx] - w[e.idx]);
            int hi = compress(ty[e.idx] + w[e.idx] + 1);
            fw.update(lo, e.delta);
            fw.update(hi, -e.delta);
        } else {
            cnt[e.idx] = fw.query(compress(ty[e.idx]));
        }
    }

    vector<int> result;
    for(int i = 0; i < n; i++) {
        if(cnt[i] - 1 >= k) {
            result.push_back(i + 1);
        }
    }

    cout << result.size() << "\n";
    for(int i = 0; i < (int)result.size(); i++) {
        if(i) {
            cout << " ";
        }
        cout << result[i];
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p394.in1
======================
2 1
0 0 1
1 0 1

=================
p394.in2
======================
3 2
0 0 1
1 0 1
10 3 1

=================
p394.in3
======================
3 2
0 0 100
13 17 5
10 10 10

=================
statement.txt
======================
394. Berhatton
Time limit per test: 1.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Berhatton is one of the most picturesque districts of Berland. All streets in Berhatton are parallel to the coordinate axes. All streets are really long, so you can consider them infinite. Any point with integer coordinates is an intersection of two streets. So the whole plane is divided by streets into one-unit squares. All squares are occupied by the sky-scrappers. Due to this fact, the distance between point (x1, y1) and point (x2, y2) is equal to |x1 - x2| + |y1 - y2|. BerPizza company has been working in Berhatton for a while and has N pizza huts. In each pizza hut they can make any kind of pizza from the menu and deliver it to the customer. Unfortunately, the company doesn't have enough funds to buy cars or even bikes for pizza delivery, so pizza boys have to deliver pizza on foot. Pizza boys from different huts run with the different speed. Everybody knows the famous motto of BerPizza "Deliver pizza in 10 minutes", so pizza boys have to move fast.

Nowadays BerPizza company has a hard time, because hamburgers become more and more popular. BerPizza has even decided to close some of their huts because of financial problems. BerPizza president has made a rush decision that the pizza hut A can be closed if pizza boys from at least K other pizza huts can reach it in 10 minutes. Your task is to find numbers of pizza huts, which can be closed.

Input
The first line of the input contains two integer numbers N and K (2 ≤ N ≤ 105, 1 ≤ K ≤ N - 1). The following N lines contain coordinates of pizza huts x, y, and number w — the amount of unit segments pizza boy can cover in 10 minutes (0 ≤ x ≤ 109, 0 ≤ y ≤ 109, 1 ≤ w ≤ 109).

Output
Print the number of pizza huts T which can be closed to the first line of the output file. The next line should contain T numbers — the numbers of pizza huts that need to be closed. Pizza hut numbers should be printed in increasing order. Pizza huts are numbered from 1 to N in the order they are given in the input file.

Example(s)
sample input
sample output
2 1
0 0 1
1 0 1
2
1 2

sample input
sample output
3 2
0 0 1
1 0 1
10 3 1
0

sample input
sample output
3 2
0 0 100
13 17 5
10 10 10
1
2


=================
