fork download
copy 
  1. import java.lang.*;
  2. import java.math.*;
  3. import java.util.*;
  4. import java.io.*;
  5.  
  6. public class Main {
  7.     ArrayList<Line> v=new ArrayList<>();
  8.     int blocksize=500;
  9.     int totalblocks;
  10.     ConvexHullTrick cht[];
  11.     ArrayList<Line> vec[];
  12.  
  13.  
  14.     ArrayList<Line> tmpvec=new ArrayList<>();
  15.     int n,q;
  16.  
  17.     void solve() throws Exception {
  18.         n=ni();
  19.  
  20.         blocksize=(int)Math.sqrt(n)+1;
  21.  
  22.         totalblocks=n/blocksize+1;
  23.         if(n%blocksize==0) totalblocks--;
  24.         //   pw.println(blocksize+" "+totalblocks);
  25.         cht=new ConvexHullTrick[totalblocks];
  26.         vec=new ArrayList[totalblocks];
  27.         for(int i=0;i<totalblocks;i++){
  28.             cht[i]=new ConvexHullTrick(blocksize);
  29.             vec[i]=new ArrayList<>();
  30.         }
  31.  
  32.  
  33.         for(int i=0;i<n;i++) {
  34.             long a=ni(),b=ni();
  35.             if(a>100000 || b>100000) throw new Exception("out of bound");
  36.  
  37.             //  cht[i/blocksize].add_line(a,b);
  38.             vec[i/blocksize].add(new Line(a,b));
  39.         }
  40.         for(int i=0;i<totalblocks;i++){
  41.             tmpvec.clear();
  42.             for(Line l : vec[i]) tmpvec.add(new Line(-l.a,-l.b));
  43.             Collections.sort(tmpvec);
  44.             for(Line l : tmpvec) cht[i].add_line(l.a,l.b);
  45.         }
  46.         q=ni();
  47.  
  48.         int cnt=0;
  49.         for(int qu=0;qu<q;qu++) {
  50.             int type =ni();
  51.  
  52.             if (type == 1) {
  53.                 int i1 = ni(), i2 = ni();
  54.                 int st = 0, ed = 0;
  55.                 while (i1 > vec[st].size()) {
  56.                     i1 -= vec[st].size();
  57.                     st++;
  58.                 }
  59.                 while (i2 > vec[ed].size()) {
  60.                     i2 -= vec[ed].size();
  61.                     ed++;
  62.                 }
  63.                 if (st == ed) {
  64.                     Line l = vec[st].remove(i1 - 1);
  65.                     vec[st].add(i2 - 1, l);
  66.  
  67.                 } else {
  68.                     Line l = vec[st].remove(i1 - 1);
  69.                     vec[ed].add(i2, l);
  70.  
  71.                     cht[st]=new ConvexHullTrick(vec[st].size());
  72.                     cht[ed]=new ConvexHullTrick(vec[ed].size());
  73.                     tmpvec.clear();
  74.                     for(Line p : vec[st]) tmpvec.add(new Line(-p.a,-p.b));
  75.                     Collections.sort(tmpvec);
  76.                     for(Line p : tmpvec) cht[st].add_line(p.a,p.b);
  77.                     tmpvec.clear();
  78.                     for(Line p : vec[ed]) tmpvec.add(new Line(-p.a,-p.b));
  79.                     Collections.sort(tmpvec);
  80.                     for(Line p : tmpvec) cht[ed].add_line(p.a,p.b);
  81.  
  82.  
  83.                 }
  84.                 // for(Line l : vec[st]) pw.println(l.a+" "+l.b);
  85.                 cnt++;
  86.                 if (cnt == blocksize) {
  87.                     cnt = 0;
  88.                     rebuild();
  89.                 }
  90.             } else {
  91.                 int l = ni(), r =ni() ;
  92.                 int x = ni();
  93.                 int st = 0, ed = 0;
  94.                 if(x>100000) throw new Exception("out of bound");
  95.  
  96.                 while (l > vec[st].size()) {
  97.                     l -= vec[st].size();
  98.                     st++;
  99.                 }
  100.                 while (r > vec[ed].size()) {
  101.                     r -= vec[ed].size();
  102.                     ed++;
  103.                 }
  104.                 // pw.println(st+" "+ed+" "+l+" "+r);
  105.                 long ans = Long.MIN_VALUE;
  106.                 //  pw.println(st+" "+ed);
  107.                 if(st==ed){
  108.                     for(int i=l-1;i<r;i++) {
  109.                         Line p=vec[st].get(i);
  110.                         ans=Math.max(ans,p.get(x));
  111.                     }
  112.                 }else {
  113.                     for (int i = st + 1; i < ed; i++) ans = Math.max(ans, -cht[i].querry(x));
  114.                     for (int i = l - 1; i < vec[st].size(); i++) {
  115.                         Line p = vec[st].get(i);
  116.                         ans = Math.max(ans, p.get(x));
  117.                     }
  118.                     for (int i = 0; i < r; i++) {
  119.                         Line p = vec[ed].get(i);
  120.                         ans = Math.max(ans, p.get(x));
  121.                     }
  122.                 }
  123.  
  124.                 pw.println(ans);
  125.             }
  126.  
  127.         }
  128.  
  129.  
  130.     }
  131.     void rebuild(){
  132.         v.clear();
  133.         for(int i=0;i<totalblocks;i++) cht[i]=new ConvexHullTrick(blocksize);
  134.         for(int i=0;i<totalblocks;i++){
  135.             v.addAll(vec[i]);
  136.             vec[i].clear();
  137.  
  138.         }
  139.         for(int i=0;i<v.size();i++){
  140.             Line l=v.get(i);
  141.             vec[i/blocksize].add(new Line(l.a,l.b));
  142.  
  143.         }
  144.         for(int i=0;i<totalblocks;i++){
  145.             tmpvec.clear();
  146.             for(Line l : vec[i]) tmpvec.add(new Line(-l.a,-l.b));
  147.             Collections.sort(tmpvec);
  148.             for(Line l : tmpvec) cht[i].add_line(l.a,l.b);
  149.         }
  150.  
  151.  
  152.  
  153.     }
  154.     static class ConvexHullTrick {
  155.         int size;
  156.         Line lines[];
  157.         Line hull[];
  158.  
  159.         public ConvexHullTrick(int len){
  160.             size=0;
  161.             // lines=new Line[len];
  162.             hull=new Line[len];
  163.         }
  164.         boolean isbad(int prev,int curr,int next){
  165.             Line l1=hull[prev],l2=hull[curr],l3=hull[next];
  166. //            if((l1.b-l3.b)>Long.MAX_VALUE/(l2.a-l1.a) || (l1.b-l2.b)>Long.MAX_VALUE/(l3.a-l1.a) ){
  167. //                return  ((l1.b-l3.b)*1.0)/(l3.a-l1.a) <=((l1.b-l2.b)*1.0)/(l2.a-l1.a);
  168. //            }
  169.             return (double)(l1.b-l3.b)*(l2.a-l1.a)<=(double)(l1.b-l2.b)*(l3.a-l1.a);
  170.         }
  171.  
  172.         void add_line(long a,long b){
  173.             if(size!=0 && hull[size-1].a==a) return;
  174.             hull[size++]=new Line(a,b);
  175.             while(size>2 && isbad(size-3,size-2,size-1)){
  176.                 hull[size-2]=hull[size-1];
  177.                 size--;
  178.             }
  179.         }
  180.         void add_lines(){
  181.             Arrays.sort(lines, new Comparator<Line>() {
  182.                 @Override
  183.                 public int compare(Line t1, Line t2) {
  184.                     int t=Long.compare(t2.a,t1.a);
  185.                     if(t!=0) return t;
  186.                     t=Long.compare(t1.b,t2.b);
  187.                     return t;
  188.                 }
  189.             });
  190.             for(Line l : lines) add_line(l.a,l.b);
  191.         }
  192.         long querry(long x){
  193.  
  194.             if(size==0) return Long.MAX_VALUE;
  195.             int l=0,r=size-1;
  196.             long ans=Long.MAX_VALUE;
  197.  
  198.             while(l<=r){
  199.                 int mid=(l+r)/2;
  200.                 if(mid>0 && x*(hull[mid-1].a-hull[mid].a)<((hull[mid].b-hull[mid-1].b))){
  201.                     r=mid-1;
  202.                 }else if(mid+1<size && x*(hull[mid].a-hull[mid+1].a)>((hull[mid+1].b-hull[mid].b))){
  203.                     l=mid+1;
  204.                 }else {
  205.                     ans=Math.min(ans,hull[mid].get(x));
  206.                     break;
  207.                 }
  208.             }
  209.  
  210.  
  211.             return ans;
  212.         }
  213.     }
  214.  
  215.     static class Line implements Comparable<Line>{
  216.         long a;
  217.         long b;
  218.         public Line(long a,long b){
  219.             this.a=a;
  220.             this.b=b;
  221.         }
  222.         long get(long x){
  223.             return a*x+b;
  224.         }
  225.         public int compareTo(Line c){
  226.             int t=Long.compare(c.a,this.a);
  227.             if(t!=0) return t;
  228.             t=Long.compare(this.b,c.b);
  229.             return t;
  230.         }
  231.     }
  232.     static class Line2 {
  233.         long a;
  234.         long b;
  235.         int id;
  236.         public Line2(int id,long a,long b){
  237.             this.a=a;
  238.             this.b=b;
  239.             this.id=id;
  240.         }
  241.         long get(long x){
  242.             return a*x+b;
  243.         }
  244.     }
  245.  
  246.     static int randInt(int min,int max){
  247.         Random rand=new Random();
  248.         int randInt=rand.nextInt((max-min)+1)+min;
  249.         return randInt;
  250.     }
  251.  
  252.  
  253.  
  254.  
  255.     long M= (long)1e9+7;
  256.     InputStream is;
  257.     PrintWriter pw;
  258.     String INPUT = "";
  259.     void run() throws Exception {
  260.         is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
  261.         pw = new PrintWriter(System.out);
  262.         long s = System.currentTimeMillis();
  263.         solve();
  264.         pw.flush();
  265.         if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
  266.  
  267.     }
  268.     public static void main(String[] args) throws Exception { new Main().run(); }
  269.  
  270.     private byte[] inbuf = new byte[1024];
  271.     public int lenbuf = 0, ptrbuf = 0;
  272.  
  273.     private int readByte() {
  274.         if(lenbuf == -1)throw new InputMismatchException();
  275.         if(ptrbuf >= lenbuf){
  276.             ptrbuf = 0;
  277.             try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
  278.             if(lenbuf <= 0)return -1;
  279.         }
  280.         return inbuf[ptrbuf++];
  281.     }
  282.  
  283.     private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
  284.     private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
  285.  
  286.     private double nd() { return Double.parseDouble(ns()); }
  287.     private char nc() { return (char)skip(); }
  288.  
  289.     private String ns() {
  290.         int b = skip();
  291.         StringBuilder sb = new StringBuilder();
  292.         while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
  293.             sb.appendCodePoint(b);
  294.             b = readByte();
  295.         }
  296.         return sb.toString();
  297.     }
  298.  
  299.     private char[] ns(int n) {
  300.         char[] buf = new char[n];
  301.         int b = skip(), p = 0;
  302.         while(p < n && !(isSpaceChar(b))){
  303.             buf[p++] = (char)b;
  304.             b = readByte();
  305.         }
  306.         return n == p ? buf : Arrays.copyOf(buf, p);
  307.     }
  308.  
  309.     private char[][] nm(int n, int m) {
  310.         char[][] map = new char[n][];
  311.         for(int i = 0;i < n;i++)map[i] = ns(m);
  312.         return map;
  313.     }
  314.  
  315.     private int[] na(int n) {
  316.         int[] a = new int[n];
  317.         for(int i = 0;i < n;i++)a[i] = ni();
  318.         return a;
  319.     }
  320.  
  321.     private int ni() {
  322.         int num = 0, b;
  323.         boolean minus = false;
  324.         while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
  325.         if(b == '-'){
  326.             minus = true;
  327.             b = readByte();
  328.         }
  329.  
  330.         while(true){
  331.             if(b >= '0' && b <= '9'){
  332.                 num = num * 10 + (b - '0');
  333.             }else{
  334.                 return minus ? -num : num;
  335.             }
  336.             b = readByte();
  337.         }
  338.     }
  339.  
  340.     private long nl() {
  341.         long num = 0;
  342.         int b;
  343.         boolean minus = false;
  344.         while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
  345.         if(b == '-'){
  346.             minus = true;
  347.             b = readByte();
  348.         }
  349.  
  350.         while(true){
  351.             if(b >= '0' && b <= '9'){
  352.                 num = num * 10 + (b - '0');
  353.             }else{
  354.                 return minus ? -num : num;
  355.             }
  356.             b = readByte();
  357.         }
  358.     }
  359.     private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
  360.     private void tr(Object... o) { if(INPUT.length() > 0)System.out.println(Arrays.deepToString(o)); }
  361.  
  362. }
Success #stdin #stdout 0.04s 2184192KB
comments (?)
stdin
copy 
5 
2 2 
4 5
1 3
3 6
7 1
3
2 2 3 3
1 2 4
2 2 3 3
stdout
copy 
17
15
https://ideone.com/V9kgLg
language:
Java (HotSpot 12)
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!