#72184 (Java) No.335 門松宝くじ

• 問題: No.335 門松宝くじ
• ユーザー: holeguma
• 提出日時: 2016-01-19 22:48:04
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 780 ms / 2,000 ms
• コード長: 5,576 bytes
• コンパイル時間: 2,356 ms
• コンパイル使用メモリ: 79,916 KB
• 実行使用メモリ: 45,172 KB
• 最終ジャッジ日時: 2024-09-21 14:37:48
• 合計ジャッジ時間: 8,753 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 4
other	AC * 10

ソースコード

import java.io.InputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.math.BigInteger;

public class Main{

static PrintWriter out;
static InputReader ir;

static void solve(){
 int n=ir.nextInt();
 int m=ir.nextInt();
 int ma=-1,ind=-1;
 for(int i=0;i<m;i++){
  int[] a=ir.nextIntArray(n);
  for(int j=0;j<n;j++) a[j]--;
  int[] p=new int[n];
  for(int j=0;j<n;j++) p[a[j]]=j;
  SegmentTreeRMQ st=new SegmentTreeRMQ(a);
  int tot=0;
  for(int j=0;j<n;j++){
   for(int k=j+1;k<n;k++){
    int t,ma2=-1;
    if(p[j]<p[k]){
     if(p[j]!=0){
      t=(int)st.max(0,p[j]);
      if(t>j) ma2=Math.max(ma2,Math.max(t,k));
     }
     if(p[j]+1!=p[k]){
      t=(int)st.max(p[j]+1,p[k]);
      if(t>k) ma2=Math.max(ma2,t);
      t=(int)st.min(p[j]+1,p[k]);
      if(t<j) ma2=Math.max(ma2,k);
     }
     if(p[k]!=n-1){
      t=(int)st.min(p[k]+1,n);
      if(t<k) ma2=Math.max(ma2,k);
     }
    }
    else{
     if(p[k]!=0){
      t=(int)st.min(0,p[k]);
      if(t<k) ma2=Math.max(ma2,k);
     }
     if(p[k]+1!=p[j]){
      t=(int)st.max(p[k]+1,p[j]);
      if(t>k) ma2=Math.max(ma2,t);
      t=(int)st.min(p[k]+1,p[j]);
      if(t<j) ma2=Math.max(ma2,k);
     }
     if(p[j]!=n-1){
      t=(int)st.max(p[j]+1,n);
      if(t>j) ma2=Math.max(ma2,Math.max(k,t));
     }
    }
    tot+=ma2+1;
   }
  }
  if(tot>ma){
   ma=tot;
   ind=i;
  }
 }
 out.println(ind);
}

static class SegmentTreeRMQ{

 private int n;
 private long[] mi_seg,ma_seg;
 
 public SegmentTreeRMQ(int nn) {
  n=1;
  while(n<nn) n<<=1;
  mi_seg=new long[(n<<1)-1];
  ma_seg=new long[(n<<1)-1];
  Arrays.fill(mi_seg,Long.MAX_VALUE);
  Arrays.fill(ma_seg,Long.MIN_VALUE);
 }

 public SegmentTreeRMQ(int[] a){
  int nn=a.length;
  n=1;
  while(n<nn) n<<=1;
  mi_seg=new long[(n<<1)-1];
  ma_seg=new long[(n<<1)-1];
  Arrays.fill(mi_seg,Long.MAX_VALUE);
  Arrays.fill(ma_seg,Long.MIN_VALUE);
  for(int i=0;i<nn;i++){
   update(i,(long)a[i]);
  }
 }

 public long min(int a,int b){return _min_query(a,b,0,0,n);}

 private long _min_query(int a,int b,int k,int l,int r) {
  if (a<=l&&r<=b) return mi_seg[k];
  if (r<=a||b<=l) return Long.MAX_VALUE;
  long cl=_min_query(a, b, (k<<1)+1,l,(l+r)>>>1);
  long cr=_min_query(a, b, (k<<1)+ 2,(l+r)>>>1,r);
  return Math.min(cl,cr);
 }
 
 public void min_update(int i,long val) {
  i+=n-1;
  mi_seg[i]=val;
  while(i>0) {
   i--; i>>>=1;
   mi_seg[i]=Math.min(mi_seg[(i<<1)+1],mi_seg[(i<<1)+2]);
  }
 }

 public long max(int a,int b){return _max_query(a,b,0,0,n);}

 private long _max_query(int a,int b,int k,int l,int r) {
  if (a<=l&&r<=b) return ma_seg[k];
  if (r<=a||b<=l) return Long.MIN_VALUE;
  long cl=_max_query(a, b, (k<<1)+1,l,(l+r)>>>1);
  long cr=_max_query(a, b, (k<<1)+ 2,(l+r)>>>1,r);
  return Math.max(cl,cr);
 }
 
 public void max_update(int i,long val) {
  i+=n-1;
  ma_seg[i]=val;
  while(i>0) {
   i--; i>>>=1;
   ma_seg[i]=Math.max(ma_seg[(i<<1)+1],ma_seg[(i<<1)+2]);
  }
 }

 public void update(int i,long val) {
  min_update(i,val);
  max_update(i,val);
 }
}

public static void main(String[] args) throws Exception{
 ir=new InputReader(System.in);
 out=new PrintWriter(System.out);
 solve();
 out.flush();
}

static class InputReader {
 private InputStream in;
 private byte[] buffer=new byte[1024];
 private int curbuf;
 private int lenbuf;

 public InputReader(InputStream in) {this.in=in; this.curbuf=this.lenbuf=0;}
 
 public boolean hasNextByte() {
  if(curbuf>=lenbuf){
   curbuf= 0;
   try{
    lenbuf=in.read(buffer);
   }catch(IOException e) {
    throw new InputMismatchException();
   }
   if(lenbuf<=0) return false;
  }
  return true;
 }

 private int readByte(){if(hasNextByte()) return buffer[curbuf++]; else return -1;}
 
 private boolean isSpaceChar(int c){return !(c>=33&&c<=126);}
 
 private void skip(){while(hasNextByte()&&isSpaceChar(buffer[curbuf])) curbuf++;}
 
 public boolean hasNext(){skip(); return hasNextByte();}
 
 public String next(){
  if(!hasNext()) throw new NoSuchElementException();
  StringBuilder sb=new StringBuilder();
  int b=readByte();
  while(!isSpaceChar(b)){
   sb.appendCodePoint(b);
   b=readByte();
  }
  return sb.toString();
 }
 
 public int nextInt() {
  if(!hasNext()) throw new NoSuchElementException();
  int c=readByte();
  while (isSpaceChar(c)) c=readByte();
  boolean minus=false;
  if (c=='-') {
   minus=true;
   c=readByte();
  }
  int res=0;
  do{
   if(c<'0'||c>'9') throw new InputMismatchException();
   res=res*10+c-'0';
   c=readByte();
  }while(!isSpaceChar(c));
  return (minus)?-res:res;
 }
 
 public long nextLong() {
  if(!hasNext()) throw new NoSuchElementException();
  int c=readByte();
  while (isSpaceChar(c)) c=readByte();
  boolean minus=false;
  if (c=='-') {
   minus=true;
   c=readByte();
  }
  long res = 0;
  do{
   if(c<'0'||c>'9') throw new InputMismatchException();
   res=res*10+c-'0';
   c=readByte();
  }while(!isSpaceChar(c));
  return (minus)?-res:res;
 }

 public double nextDouble(){return Double.parseDouble(next());}

 public BigInteger nextBigInteger(){return new BigInteger(next());}

 public int[] nextIntArray(int n){
  int[] a=new int[n];
  for(int i=0;i<n;i++) a[i]=nextInt();
  return a;
 }

 public long[] nextLongArray(int n){
  long[] a=new long[n];
  for(int i=0;i<n;i++) a[i]=nextLong();
  return a;
 }

 public char[][] nextCharMap(int n,int m){
  char[][] map=new char[n][m];
  for(int i=0;i<n;i++) map[i]=next().toCharArray();
  return map;
 }
}
}