結果
問題 | No.911 ラッキーソート |
ユーザー |
![]() |
提出日時 | 2019-10-18 23:46:39 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 371 ms / 2,000 ms |
コード長 | 1,699 bytes |
コンパイル時間 | 3,239 ms |
コンパイル使用メモリ | 77,688 KB |
実行使用メモリ | 66,232 KB |
最終ジャッジ日時 | 2024-06-25 20:03:47 |
合計ジャッジ時間 | 14,618 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;public class Main {public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] sa = br.readLine().split(" ");int n = Integer.parseInt(sa[0]);long l = Long.parseLong(sa[1]) - 1;long r = Long.parseLong(sa[2]);sa = br.readLine().split(" ");long[] a = new long[n];for (int i = 0; i < n; i++) {a[i] = Long.parseLong(sa[i]);}br.close();int[] dp = new int[62];Arrays.fill(dp, 2);for (int i = 1; i < n; i++) {for (int j = 61; j >= 0; j--) {long x = a[i - 1] >> j & 1;long y = a[i] >> j & 1;if (x > y) {if (dp[j] == 0) {System.out.println(0);return;}dp[j] = 1;break;}if (x < y) {if (dp[j] == 1) {System.out.println(0);return;}dp[j] = 0;break;}}}long[][] bdp1 = bdp(dp, r);long[][] bdp2 = bdp(dp, l);System.out.println(bdp1[0][0] + bdp1[0][1] - bdp2[0][0] - bdp2[0][1]);}static long[][] bdp(int[] dp, long r) {long[][] bdp = new long[62][2];if (r < 0) {return bdp;}bdp[61][0] = 1;for (int j = 60; j >= 0; j--) {bdp[j][1] = bdp[j + 1][1];if (dp[j] == 0) {if ((r >> j & 1) == 0) {bdp[j][0] = bdp[j + 1][0];} else {bdp[j][1] += bdp[j + 1][0];}} else if (dp[j] == 1) {if ((r >> j & 1) == 1) {bdp[j][0] = bdp[j + 1][0];}} else {bdp[j][1] += bdp[j + 1][1];bdp[j][0] = bdp[j + 1][0];if ((r >> j & 1) == 1) {bdp[j][1] += bdp[j + 1][0];}}}return bdp;}}