結果
| 問題 |
No.404 部分門松列
|
| ユーザー |
 37zigen
|
| 提出日時 | 2016-08-07 20:42:37 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,912 bytes |
| コンパイル時間 | 4,194 ms |
| コンパイル使用メモリ | 81,480 KB |
| 実行使用メモリ | 64,280 KB |
| 最終ジャッジ日時 | 2024-11-07 07:26:11 |
| 合計ジャッジ時間 | 34,167 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 WA * 1 |
| other | AC * 9 WA * 22 |
ソースコード
package No400番台;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
public class Q404{
static InputStream is;
static PrintWriter out;
static String INPUT = "";
void solver() {
int N = ni();
int[] a = na(N);
int[] b = Arrays.copyOf(a, a.length);
Arrays.sort(b);
b = shrink(b);
int n = b.length;
BinaryIndexedTree[] B = new BinaryIndexedTree[2];
B[0] = new BinaryIndexedTree(n);
B[1] = new BinaryIndexedTree(n);
for (int i = 0; i < N; i++) {
a[i] = upper_bound(b, a[i]) + 1;
}
int[] r = new int[n + 1];
int[] l = new int[n + 1];
for (int i = 0; i < N; i++) {
r[a[i]]++;
B[1].add(a[i], 1);
}
r[a[0]]--;
long same = 0;
long[] calc = new long[n + 1];
for (int i = 0; i < N; i++) {
long ans = 0;
B[1].add(a[i], -1);
ans += B[0].sum(a[i] - 1) * B[1].sum(a[i] - 1);
ans += (i - B[0].sum(a[i])) * (N - i - 1 - B[1].sum(a[i]));
ans -= same - l[a[i]] * r[a[i]];
if (i + 1 < N) {
r[a[i + 1]]--;
same += r[a[i]];
same -= l[a[i + 1]];
l[a[i]]++;
}
B[0].add(a[i], 1);
calc[a[i]] += ans;
}
long[] sum = new long[n + 2];
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + calc[i];
}
sum[n+1]=sum[n];
int q = ni();
int[] L = new int[q];
int[] H = new int[q];
// tr(sum);
// tr(b);
for (int i = 0; i < q; i++) {
L[i] = ni();
H[i] = ni();
int low = lower_bound(b, L[i]) + 1;
int high = upper_bound(b, H[i]) + 1;
System.out.println((sum[high] - sum[low]));
// System.out.println(L[i]+" "+H[i]+" "+lower_bound(b, L[i]) + " " + upper_bound(b, H[i]));
}
}
int upper_bound(int[] d, int a) {
int min = 0;
int max = d.length;
for (int i = 0; Math.pow(2, i) < d.length + 5; i++) {
int mid = (max + min) / 2;
if (d[mid] > a) {
max = mid;
} else {
min = mid;
}
if (max == min + 1 && d[min] == a)
return min;
}
return min;
}
int lower_bound(int[] d, int a) {
int min = 0;
int max = d.length;
for (int i = 0; Math.pow(2, i) < d.length + 5; i++) {
int mid = (max + min) / 2;
if (d[mid] >= a) {
max = mid;
} else {
min = mid;
}
}
return min;
}
static int[] shrink(int[] arr) {
ArrayList<Integer> d = new ArrayList<>();
d.add(arr[0]);
for (int i = 0; i < arr.length; i++) {
if (d.get(d.size() - 1) == arr[i])
continue;
else {
d.add(arr[i]);
}
}
int[] ret = new int[d.size()];
for (int i = 0; i < ret.length; i++) {
ret[i] = d.get(i);
}
return ret;
}
class BinaryIndexedTree {
int n;
int[] d;
BinaryIndexedTree(int n) {
this.n = n;
d = new int[n + 2];
}
void add(int i, int diff) {
while (i <= n) {
d[i] += diff;
i += (i & (-i));
}
}
// sum[1,i]
int sum(int i) {
int s = 0;
while (i > 0) {
s += d[i];
i -= (i & (-i));
}
return s;
}
// sum[r,l]
int sum(int r, int l) {
return sum(l) - sum(r - 1);
}
}
public static void main(String[] args) throws Exception {
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
new Q404().solver();
out.flush();
}
static long nl() {
try {
long num = 0;
boolean minus = false;
while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'))
;
if (num == '-') {
num = 0;
minus = true;
} else {
num -= '0';
}
while (true) {
int b = is.read();
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
} catch (IOException e) {
}
return -1;
}
static char nc() {
try {
int b = skip();
if (b == -1)
return 0;
return (char) b;
} catch (IOException e) {
}
return 0;
}
static double nd() {
try {
return Double.parseDouble(ns());
} catch (Exception e) {
}
return 0;
}
static String ns() {
try {
int b = skip();
StringBuilder sb = new StringBuilder();
if (b == -1)
return "";
sb.append((char) b);
while (true) {
b = is.read();
if (b == -1)
return sb.toString();
if (b <= ' ')
return sb.toString();
sb.append((char) b);
}
} catch (IOException e) {
}
return "";
}
public static char[] ns(int n) {
char[] buf = new char[n];
try {
int b = skip(), p = 0;
if (b == -1)
return null;
buf[p++] = (char) b;
while (p < n) {
b = is.read();
if (b == -1 || b <= ' ')
break;
buf[p++] = (char) b;
}
return Arrays.copyOf(buf, p);
} catch (IOException e) {
}
return null;
}
private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}
private long[] nal(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nl();
return a;
}
public static byte[] nse(int n) {
byte[] buf = new byte[n];
try {
int b = skip();
if (b == -1)
return null;
is.read(buf);
return buf;
} catch (IOException e) {
}
return null;
}
static int skip() throws IOException {
int b;
while ((b = is.read()) != -1 && !(b >= 33 && b <= 126))
;
return b;
}
static boolean eof() {
try {
is.mark(1000);
int b = skip();
is.reset();
return b == -1;
} catch (IOException e) {
return true;
}
}
static int ni() {
try {
int num = 0;
boolean minus = false;
while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'))
;
if (num == '-') {
num = 0;
minus = true;
} else {
num -= '0';
}
while (true) {
int b = is.read();
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
} catch (IOException e) {
}
return -1;
}
static void tr(Object... o) {
System.out.println(Arrays.deepToString(o));
}
}