Advertisement
cosenza987

Untitled

Mar 22nd, 2023
1,070
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5 + 7, LOG = 20;
  6. const int N_ = N * LOG, MAX = 1e9;
  7. const long long linf = 9e18;
  8.  
  9. struct line {
  10.     long long m, b;
  11.     long long operator()(long long x) const {
  12.         return m * x + b;
  13.     }
  14.     bool cmp(const line &a, long long x) {
  15.         return (*this)(x) < a(x);
  16.     }
  17. };
  18.  
  19. namespace pli {
  20.     line seg[N_];
  21.     int roots[N], L[N_], R[N_], cnt = 1;
  22.     void insert(int x, line a, int pcur = -1, int p = -1, long long l = -MAX, long long r = MAX) {
  23.         if(pcur == -1) {
  24.             pcur = roots[x] = cnt++;
  25.         }
  26.         if(p == -1) {
  27.             p = roots[x - 1];
  28.         }
  29.         seg[pcur] = seg[p];
  30.         L[pcur] = L[p];
  31.         R[pcur] = R[p];
  32.         long long mid = (l + r) >> 1;
  33.         if(seg[p].cmp(a, mid)) {
  34.             seg[pcur] = a;
  35.             a = seg[p];
  36.         }
  37.         if(a.b == -linf) {
  38.             return;
  39.         }
  40.         if(seg[pcur].cmp(a, l) != seg[pcur].cmp(a, mid)) {
  41.             L[pcur] = cnt++;
  42.             insert(x, a, L[pcur], L[p], l, mid - 1);
  43.         } else if(seg[pcur].cmp(a, r) != seg[pcur].cmp(a, mid)) {
  44.             R[pcur] = cnt++;
  45.             insert(x, a, R[pcur], R[p], mid + 1, r);
  46.         }
  47.     }
  48.     long long query(int p, long long x, long long l = -MAX, long long r = MAX) {
  49.         long long mid = (l + r) >> 1, calc = seg[p](x);
  50.         if(calc == -linf) {
  51.             return calc;
  52.         }
  53.         if(x < mid) {
  54.             return max(calc, query(L[p], x, l, mid - 1));
  55.         } else {
  56.             return max(calc, query(R[p], x, mid + 1, r));
  57.         }
  58.     }
  59. }
  60.  
  61. int main() {
  62.     ios_base::sync_with_stdio(false);
  63.     cin.tie(nullptr);
  64.     pli::seg[0] = {0, -linf};
  65.     int n;
  66.     cin >> n;
  67.     vector<pair<long long, long long>> p(n);
  68.     for(int i = 0; i < n; i++) {
  69.         cin >> p[i].first >> p[i].second;
  70.     }
  71.     int m;
  72.     cin >> m;
  73.     for(int i = 1; i <= m; i++) {
  74.         long long mm, b;
  75.         cin >> mm >> b;
  76.         pli::insert(i, {mm, b});
  77.     }
  78.     vector<vector<int>> ans(m + 2);
  79.     for(int i = 0; i < n; i++) {
  80.         int l = 1, r = m, cur = m + 1;
  81.         while(l <= r) {
  82.             int mid = (l + r) >> 1;
  83.             if(p[i].second < pli::query(pli::roots[mid], p[i].first)) {
  84.                 cur = mid;
  85.                 r = mid - 1;
  86.             } else {
  87.                 l = mid + 1;
  88.             }
  89.         }
  90.         ans[cur].push_back(i + 1);
  91.     }
  92.     for(int i = 1; i <= m; i++) {
  93.         cout << ans[i].size() << " ";
  94.         for(auto e : ans[i]) {
  95.             cout << e << " ";
  96.         }
  97.         cout << "\n";
  98.     }
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement