fork download 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7. typedef long long lld;
  8. const int N=100005;
  9. int n,q,Lt;
  10. int a[N],b[N];
  11. int List[N];
  12. struct Node{
  13.     int l,r;
  14.     Node *lc,*rc;
  15.     vector <int> L;
  16. }Tr[N*6];
  17.  
  18. bool cmp(int i,int j){
  19.     if (a[i]>a[j]) return true;
  20.     if (a[i]<a[j]) return false;
  21.     return b[i]>b[j];
  22. }
  23.  
  24. void Select(){
  25.     int tmp=Lt;
  26.     Lt=0;
  27.     List[Lt++]=List[0];
  28.     for (int i=1;i<tmp;i++){
  29.         if (b[List[i]]<=b[List[Lt-1]]) continue;
  30.         List[Lt++]=List[i];
  31.     }
  32. }
  33.  
  34. void Form(){
  35.     int tmp=Lt;
  36.     Lt=0;
  37.     List[Lt++]=List[0];
  38.     #define x List[i]
  39.     #define y List[Lt-1]
  40.     #define z List[Lt-2]
  41.     for (int i=1;i<tmp;i++){
  42.         while (Lt>1 && (lld)(a[x]-a[y])*(b[z]-b[y])<=(lld)(a[y]-a[z])*(b[y]-b[x])) Lt--;
  43.         List[Lt++]=List[i];
  44.     }
  45.     #undef x
  46.     #undef y
  47.     #undef z
  48. }
  49.  
  50. void Make(Node *p){
  51.     Lt=0;
  52.     for (int i=p->l;i<=p->r;i++)
  53.       List[Lt++]=i;
  54.     sort(List,List+Lt,cmp);
  55.     Select();
  56.     Form();
  57.     p->L.resize(Lt);
  58.     for (int i=0;i<Lt;i++)
  59.       p->L[i]=List[i];
  60. }
  61.  
  62. void build(int p,int l,int r){
  63.     Tr[p].l=l; Tr[p].r=r; Tr[p].L.clear(); Make(&Tr[p]);
  64.     if (l==r){
  65.         Tr[p].lc=Tr[p].rc=NULL;
  66.         return;
  67.     }
  68.     Tr[p].lc=&Tr[p*2];
  69.     Tr[p].rc=&Tr[p*2+1];
  70.     build(p*2,l,(l+r)/2);
  71.     build(p*2+1,(l+r)/2+1,r);
  72. }
  73.  
  74. int Get_Best(vector<int> &L,lld t){
  75.     int S=L.size();
  76.     int l=0,r=S-1,mid;
  77.     while (l<r){
  78.         mid=(l+r)/2;
  79.         if (a[L[mid]]+t*b[L[mid]]<=a[L[mid+1]]+t*b[L[mid+1]])
  80.             l=mid+1;
  81.         else
  82.             r=mid;
  83.     }
  84.     return L[l];
  85. }
  86.  
  87. int Get_Max(int i,int j,lld t){
  88.     if (a[i]+t*b[i]>a[j]+t*b[j]) return i;
  89.     return j;
  90. }
  91.  
  92. int Get_value(Node *p,int l,int r,int t){
  93.     if (l<=p->l && p->r<=r)
  94.         return Get_Best(p->L,t);
  95.     int mid=(p->l+p->r)/2;
  96.     if (l<=mid && r>mid) return Get_Max(Get_value(p->lc,l,r,t),Get_value(p->rc,l,r,t),t);
  97.     if (l<=mid) return Get_value(p->lc,l,r,t);
  98.            else return Get_value(p->rc,l,r,t);
  99. }
  100.  
  101. int main(){
  102.     scanf("%d%d",&n,&q);
  103.     for (int i=1;i<=n;i++)
  104.         scanf("%d%d",&a[i],&b[i]);
  105.     build(1,1,n);
  106.     int l,r,t;
  107.     for (int i=0;i<q;i++){
  108.         scanf("%d%d%d",&l,&r,&t);
  109.         printf("%d\n",Get_value(&Tr[1],l,r,t));
  110.     }
  111. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Aga48
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!