Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Слава Україні, Героям слава
- #include <bits/stdc++.h>
- using namespace std;
- // random shit that apparently worked :D
- // 1st AC -> persistent li chao tree
- // 2nd AC -> parallel binary search + CHT
- // 3rd AC -> parallel binary search + li chao
- const int N = 1e5 + 7, MAX = 1e9;
- const long long linf = 0x3f3f3f3f3f3f3f3f;
- vector<pair<long long, long long>> pts, lines;
- vector<vector<int>> ans;
- struct lichao {
- struct line {
- long long m, b;
- long long operator()(long long x) const {
- return m * x + b;
- }
- bool cmp(const line &a, long long x) {
- return (*this)(x) < a(x);
- }
- };
- vector<line> seg;
- vector<int> L, R;
- lichao() {
- seg.push_back({0, -linf});
- L.push_back(-1);
- R.push_back(-1);
- }
- void add(line a, int p = 0, long long l = -MAX, long long r = MAX) {
- long long mid = (l + r) >> 1;
- if(seg[p].cmp(a, mid)) {
- swap(seg[p], a);
- }
- if(a.b == -linf) {
- return;
- }
- if(seg[p].cmp(a, l) != seg[p].cmp(a, mid)) {
- if(L[p] == -1) {
- L[p] = seg.size();
- R.push_back(-1);
- L.push_back(-1);
- seg.push_back({0, -linf});
- }
- add(a, L[p], l, mid - 1);
- } else if(seg[p].cmp(a, r) != seg[p].cmp(a, mid)) {
- if(R[p] == -1) {
- R[p] = seg.size();
- R.push_back(-1);
- L.push_back(-1);
- seg.push_back({0, -linf});
- }
- add(a, R[p], mid + 1, r);
- }
- }
- long long query(long long x, int p = 0, long long l = -MAX, long long r = MAX) {
- if(p < 0) {
- return -linf;
- }
- long long mid = (l + r) >> 1, calc = seg[p](x);
- if(calc == -linf) {
- return calc;
- }
- if(x < mid) {
- return max(calc, query(x, L[p], l, mid - 1));
- } else {
- return max(calc, query(x, R[p], mid + 1, r));
- }
- }
- };
- void bs(int l, int r, vector<int> &cand) {
- if(l + 1 == r or cand.empty()) {
- for(auto e : cand) {
- ans[l].push_back(e);
- }
- return;
- }
- int mid = (l + r) >> 1;
- lichao li;
- for(int i = l; i < mid; i++) {
- li.add({lines[i].first, lines[i].second});
- }
- vector<int> pode, npode;
- for(auto e : cand) {
- if(pts[e].second < li.query(pts[e].first)) {
- pode.push_back(e);
- } else {
- npode.push_back(e);
- }
- }
- bs(l, mid, pode);
- vector<int>().swap(pode);
- bs(mid, r, npode);
- vector<int>().swap(npode);
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int n;
- cin >> n;
- pts.resize(n);
- for(int i = 0; i < n; i++) {
- cin >> pts[i].first >> pts[i].second;
- }
- int p;
- cin >> p;
- lines.resize(p);
- ans.resize(p + 1);
- for(int i = 0; i < p; i++) {
- cin >> lines[i].first >> lines[i].second;
- }
- vector<int> cand(n);
- iota(cand.begin(), cand.end(), 0);
- bs(0, p + 1, cand);
- for(int i = 0; i < p; i++) {
- cout << ans[i].size() << " ";
- for(auto e : ans[i]) {
- cout << e + 1 << " ";
- }
- cout << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement