fork download
copy 
  1.        #include <bits/stdc++.h>
  2.  
  3.         #define pb push_back
  4.         #define mp make_pair
  5.  
  6.         typedef long long ll;
  7.         using namespace std;
  8.  
  9.         template<typename S, typename T>
  10.         ostream& operator<<(ostream& out,pair<S,T> const& p){out<<'('<<p.fi<<", "<<p.se<<')';return out;}
  11.  
  12.         template<typename T>
  13.         ostream& operator<<(ostream& out,vector<T> const& v){
  14.         int l=v.size();for(int i=0;i<l-1;i++)out<<v[i]<<' ';if(l>0)out<<v[l-1];return out;}
  15.  
  16.         void tr(){cout << endl;}
  17.         template<typename S, typename ... Strings>
  18.         void tr(S x, const Strings&... rest){cout<<x<<' ';tr(rest...);}
  19.  
  20.         typedef long long ll;
  21.         typedef pair<int,int> pii;
  22.  
  23.         const ll N = 50005;
  24.         int blksize;
  25.         struct line{
  26.         	ll m, c;
  27.         	ll get(ll x){
  28.  
  29.                 ll xx = 1LL*m*x;
  30.  
  31.         		return xx + c;
  32.         	}
  33.         };
  34.  
  35.  
  36.  
  37.         struct convexHull{
  38.         	ll top;
  39.             line st[250];
  40.         	bool smallerIntercept(const line &l1, const line &l2, const line &l3){
  41.         		return (l3.c - l1.c) * (l1.m - l2.m) <= (l2.c - l1.c) * (l1.m - l3.m);
  42.         	}
  43.  
  44.         	convexHull() : top(0) {	}
  45.  
  46.         	void insert(ll m, ll c){
  47.         		line l = {m, c};
  48.  
  49.         		while(top > 1 and smallerIntercept(st[top-2], st[top-1], l)) --top;
  50.         		st[top++] = l;
  51.         		return;
  52.         	}
  53.         	void clear_hull(){
  54.         	 top=0;
  55.         	}
  56.  
  57.         	ll query(ll x){
  58.         		ll lo = 0, hi = top-1, mid;
  59.  
  60.         		while(lo+1 <= hi){
  61.         			mid = (lo + hi) >> 1;
  62.         			if(st[mid].get(x) <= st[mid+1].get(x)) lo = mid+1; else hi = mid;
  63.         		}
  64.  
  65.         		//ll mx=0;
  66.         		//for(int i=0;i<=hi;i++) mx=max(mx,st[i].get(x));
  67.  
  68.  
  69.                 return st[lo].get(x);
  70.         		//return mx;
  71.         	}
  72.         };
  73.         vector<pair<ll,ll> >v;
  74.         vector<pair<ll,ll> >vec[250];
  75.         vector<pair<ll,ll> >temp;
  76.         vector<ll>vaa;
  77.  
  78.         ll n,q;
  79.  
  80.         struct convexHull cht[250];
  81.         ll a[N], sum[N], total = 0;
  82.         ll aa[N];
  83.         ll tot_blk;
  84.         ll bb[N];
  85.  
  86.         bool cmp(pair<ll,ll>v1,pair<ll,ll>v2)
  87.         {
  88.             if(v1.first<v2.first)
  89.             {
  90.                 return 1;
  91.             }
  92.             else if(v1.first>v2.first)
  93.             {
  94.                 return 0;
  95.             }
  96.             if(v1.second>v2.second)
  97.             {
  98.                 return 1;
  99.             }
  100.             return 0;
  101.         }
  102.         void rebuild()
  103.         {
  104.             temp.clear();
  105.             for(int i=0;i<tot_blk;i++)
  106.             {
  107.                 for(int j=0;j<vec[i].size();j++)
  108.                 {
  109.                     temp.pb({vec[i][j].first,vec[i][j].second});
  110.                 }
  111.                 vec[i].clear();
  112.             }
  113.             for(int i=0;i<temp.size();i++)
  114.             {
  115.                 vec[i/blksize].pb({temp[i].first,temp[i].second});
  116.             }
  117.             temp.clear();
  118.             for(int i=0;i<tot_blk;i++)
  119.             {
  120.                 temp.clear();
  121.                 for(int j=0;j<vec[i].size();j++)
  122.                 {
  123.                     int fi = vec[i][j].first;
  124.                     int se = vec[i][j].second;
  125.                     temp.pb({fi,se});
  126.                 }
  127.                 sort(temp.begin(),temp.end(),cmp);
  128.                // cht[i].clear_hull();
  129.                 cht[i] = (*new convexHull());
  130.                 for(int j=0;j<temp.size();j++)
  131.                 {
  132.                     cht[i].insert(temp[j].first,temp[j].second);
  133.                 }
  134.  
  135.             }
  136.         }
  137.         int main(){
  138.  
  139.             scanf("%lld",&n);
  140.             for(int i=0;i<n;i++)
  141.             {
  142.                 ll x,y;
  143.                 scanf("%lld %lld",&x,&y);
  144.                 v.pb({x,y});
  145.  
  146.             }
  147.             blksize = sqrt(n)+1;
  148.  
  149.             for(int i=0;i<n;i++)
  150.             {
  151.                 vec[i/blksize].pb({v[i].first,v[i].second});
  152.             }
  153.             tot_blk = n/blksize;
  154.             if(n%blksize!=0)
  155.                 tot_blk++;
  156.  
  157.  
  158.             for(int i=0;i<tot_blk;i++)
  159.             {
  160.                 temp.clear();
  161.                 for(int j=0;j<vec[i].size();j++)
  162.                 {
  163.                     int fi = vec[i][j].first;
  164.                     int se = vec[i][j].second;
  165.                     temp.pb({fi,se});
  166.                 }
  167.                 sort(temp.begin(),temp.end(),cmp);
  168.                 cht[i] = *(new convexHull());
  169.  
  170.                 for(int j=0;j<temp.size();j++)
  171.                 {
  172.                     cht[i].insert(temp[j].first,temp[j].second);
  173.                 }
  174.  
  175.             }
  176.             /*
  177.             cout<<cht[1].query(14188)<<endl;
  178.             temp.clear();
  179.             temp.pb({18173,2178});
  180.             temp.pb({32296,5322});
  181.             temp.pb({14230,29386});
  182.             sort(temp.begin(),temp.end(),cmp);
  183.             for(int j=0;j<temp.size();j++)
  184.                 {
  185.                     cht[4].insert(temp[j].first,temp[j].second);
  186.                 }
  187.             cout<<cht[4].query(14188)<<endl;
  188.           */
  189.            scanf("%lld",&q);
  190.             ll cnt = 0;
  191.  
  192.             while(q--)
  193.             {
  194.                 int type,l,r,x;
  195.                 scanf("%d",&type);
  196.                 if(type == 1)
  197.                 {
  198.                     scanf("%d %d",&l,&r);
  199.                     if(cnt == blksize)
  200.                     {
  201.                         rebuild();
  202.                         cnt=0;
  203.                     }
  204.                     cnt++;
  205.                     int st=0,ed=0;
  206.                     for(int i=0;i<tot_blk;i++)
  207.                     {
  208.                         if(vec[i].size()<l)
  209.                         {
  210.                             l-=vec[i].size();
  211.                         }
  212.                         else
  213.                         {
  214.                             st = i;
  215.                             break;
  216.                         }
  217.                     }
  218.                     for(int i=0;i<tot_blk;i++)
  219.                     {
  220.                         if(vec[i].size()<r)
  221.                         {
  222.                             r -= vec[i].size();
  223.                         }
  224.                         else
  225.                         {
  226.                             ed = i;
  227.                             break;
  228.                         }
  229.                     }
  230.                     //cout<<blksize<<" "<<tot_blk<<" "<<st<<" "<<ed<<" "<<l<<" "<<r<<endl;
  231.                     if(st == ed)
  232.                     {
  233.                         pair<ll,ll> ele = vec[st][l-1];
  234.                         vec[st].erase(vec[st].begin()+l-1);
  235.                         vector<pair<ll,ll> >::iterator it = vec[st].begin();
  236.                         vec[st].insert(vec[st].begin()+r-1,ele);
  237.  
  238.                     }
  239.                     else
  240.                     {
  241.                         pair<ll,ll> ele = vec[st][l-1];
  242.                         //cout<<"sd1"<<endl;
  243.                         vec[st].erase(vec[st].begin()+l-1);
  244.                         vector<pair<ll,ll> >::iterator it = vec[st].begin();
  245.                         vec[ed].insert(vec[ed].begin()+r,ele);
  246.                         //cout<<"sd2"<<endl;
  247.  
  248.                         temp.clear();
  249.                        // cout<<"temp array"<<endl;
  250.                         for(int i=0;i<vec[st].size();i++)
  251.                         {
  252.                             temp.pb({vec[st][i].first,vec[st][i].second});
  253.                           //  cout<<vec[st][i].first<<" "<<vec[st][i].second<<endl;
  254.                         }
  255.                         //cout<<endl;
  256.                         sort(temp.begin(),temp.end(),cmp);
  257.                         //cht[st].clear_hull();
  258.                           cht[st]=*(new convexHull());
  259.               //          cout<<"temp start"<<endl;
  260.                         for(int i=0;i<temp.size();i++)
  261.                         {
  262.                             cht[st].insert(temp[i].first,temp[i].second);
  263.                 //            cout<<temp[i].first<<" "<<temp[i].second<<endl;
  264.                         }
  265.                   //      cout<<st<<" "<<cht[st].query(14188)<<endl;
  266.                     //    cout<<"temp end"<<endl;
  267.                         temp.clear();
  268.                         for(int i=0;i<vec[ed].size();i++)
  269.                         {
  270.                             temp.pb({vec[ed][i].first,vec[ed][i].second});
  271.                         //cout<<vec[ed][i].first<<" "<<vec[ed][i].second<<endl;
  272.                         }
  273.                       //  cout<<"temp array end"<<endl;
  274.                         sort(temp.begin(),temp.end(),cmp);
  275.                       //  cout<<cht[1].query(14188)<<endl;
  276.                         //cht[ed].clear_hull();
  277.                          cht[ed]=*(new convexHull());
  278.                     //   cout<<cht[1].query(14188)<<" "<<ed<<endl;
  279.                         for(int i=0;i<temp.size();i++)
  280.                         {
  281.                             cht[ed].insert(temp[i].first,temp[i].second);
  282.                         }
  283.                        // cout<<cht[1].query(14188)<<endl;
  284.                     }
  285.  
  286.  
  287.  
  288.                 }
  289.                 else
  290.                 {
  291.                 	scanf("%d %d %d",&l,&r,&x);
  292.                     //cin>>l>>r>>x;
  293.  
  294.                     int st=0,ed=0;
  295.                     for(int i=0;i<tot_blk;i++)
  296.                     {
  297.                         if(vec[i].size()<l)
  298.                         {
  299.                             l-=vec[i].size();
  300.                         }
  301.                         else
  302.                         {
  303.                             st = i;
  304.                             break;
  305.                         }
  306.                     }
  307.                     for(int i=0;i<tot_blk;i++)
  308.                     {
  309.                         if(vec[i].size()<r)
  310.                         {
  311.                             r -= vec[i].size();
  312.                         }
  313.                         else
  314.                         {
  315.                             ed = i;
  316.                             break;
  317.                         }
  318.                     }
  319.                     ll ans = -1;
  320.     //                cout<<st<<" "<<ed<<" "<<l<<" "<<r<<" "<<blksize<<endl;
  321.                     if(st == ed)
  322.                     {
  323.                         for(int i=l-1;i<=r-1;i++)
  324.                         {
  325.                             ll m = vec[st][i].first;
  326.                             ll c = vec[st][i].second;
  327.                             ll aa = 1LL*m*x+1LL*c;
  328.                             ans = max(ans,aa);
  329.                         }
  330.                     }
  331.                     else
  332.                     {
  333.                         for(int i=l-1;i<vec[st].size();i++)
  334.                         {
  335.                             ll m = vec[st][i].first;
  336.                             ll c = vec[st][i].second;
  337.                             ll aa = 1LL*m*x+1LL*c;
  338.                             ans = max(ans,aa);
  339.                         }
  340.       //                  cout<<ans<<endl;
  341.                         for(int i=0;i<=r-1;i++)
  342.                         {
  343.                             ll m = vec[ed][i].first;
  344.                             ll c = vec[ed][i].second;
  345.                             ll aa = 1LL*m*x+1LL*c;
  346.                             ans = max(ans,aa);
  347.                         }
  348.  
  349.         //                cout<<ans<<endl;
  350.           //              cout<<cht[1].query(14188);
  351.                         for(int i=st+1;i<ed;i++)
  352.                         {
  353.                             ll aa = cht[i].query(x);
  354.                             ans = max(ans,aa);
  355.             //                cout<<"YES"<<i<<" "<<x<<" "<<aa<<endl;
  356.                             //cout<<"blk "<<i<<" "<<aa<<endl;
  357.                         }
  358.                     }
  359.                     printf("%lld\n",ans);
  360.                 }
  361.  
  362.             }
  363.  
  364.  
  365.             return 0;
  366.  
  367.         }
Success #stdin #stdout 0s 17792KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hyPb16
language:
C++14 (gcc 8.3)
created:
5 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!