結果
問題 |
No.711 競技レーティング単調増加
|
ユーザー |
|
提出日時 | 2018-07-05 14:19:59 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,275 bytes |
コンパイル時間 | 2,421 ms |
コンパイル使用メモリ | 80,336 KB |
実行使用メモリ | 76,132 KB |
最終ジャッジ日時 | 2024-07-01 02:26:44 |
合計ジャッジ時間 | 18,297 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 WA * 17 |
ソースコード
import java.io.BufferedReader; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.Map; import java.util.StringTokenizer; import java.util.TreeMap; public class Main { static int bit[]; static void update(int ind,int delta) { while (ind < bit.length) { bit[ind] = Math.max(bit[ind], delta); ind += ind & -ind; } } static int get(int ind) { int res = 0; while (ind > 0) { res = Math.max(res, bit[ind]); ind -= ind & -ind; } return res; } public static void main(String[]args) throws Throwable { Scanner sc = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); int n = sc.nextInt(); TreeMap<Integer,Integer> cord = new TreeMap(); int arr[] = new int[n]; for (int i = 0 ; i < n ; ++i) { arr[i] = sc.nextInt() - i; cord.put(arr[i], 0); } int maxVal = 1; for (Map.Entry<Integer,Integer> x : cord.entrySet()) { x.setValue(maxVal++); } int lis = 0; maxVal++; bit = new int[maxVal + 1]; for (int i = 0 ; i < n; ++i) { arr[i] = cord.get(arr[i]); } for (int i = 0 ; i < n ; ++i) { int cur = get(arr[i]) + 1; lis = Math.max(lis, cur); update(arr[i],cur); } System.out.println(n - lis); } static class Scanner { StringTokenizer st; BufferedReader br; public Scanner(InputStream s) { br = new BufferedReader(new InputStreamReader(s)); } public Scanner(String s) throws FileNotFoundException { br = new BufferedReader(new FileReader(new File(s))); } public String next() throws IOException { while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine()); return st.nextToken(); } public int nextInt() throws IOException { return Integer.parseInt(next()); } public long nextLong() throws IOException { return Long.parseLong(next()); } public String nextLine() throws IOException { return br.readLine(); } public double nextDouble() throws IOException { return Double.parseDouble(next()); } public boolean ready() throws IOException { return br.ready(); } } }