Submission #950479
Source Code Expand
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Supplier;
public class Main {
void run() {
int n = ni();
int q = ni();
int[] x = new int[n];
int[] r = new int[n];
int[] h = new int[n];
for (int i = 0; i < n; ++i) {
x[i] = ni() + 1;
r[i] = ni();
h[i] = ni();
}
BIT<Double> bit = new BIT<>(2 * 10000 + 1, (a, b) -> a + b, () -> 0.0);
for (int i = 1; i <= 2 * 10000 + 1; ++i) {
double sum = 0;
for (int j = 0; j < n; ++j) {
if (x[j] <= i && i < x[j] + h[j]) {
double h1 = h[j] - (i - x[j]);
double h2 = h[j] - (i + 1 - x[j]);
double r1 = (double) r[j] * h1 / h[j];
double r2 = (double) r[j] * h2 / h[j];
double v1 = 1.0 / 3.0 * Math.PI * r1 * r1 * h1;
double v2 = 1.0 / 3.0 * Math.PI * r2 * r2 * h2;
sum += v1 - v2;
}
}
bit.update(i, sum);
}
for (int i = 0; i < q; ++i) {
int a = ni();
int b = ni();
System.out.printf("%.6f\n", bit.reduce(b, () -> 0.0) - bit.reduce(a, () -> 0.0));
}
}
Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
new Main().run();
}
int ni() {
return Integer.parseInt(sc.next());
}
void debug(Object... os) {
System.err.println(Arrays.deepToString(os));
}
class BIT<T> {
int n;
ArrayList<T> bit;
BiFunction<T, T, T> bif;
BIT(int n, BiFunction<T, T, T> bif, Supplier<T> sup) {
this.n = n;
bit = new ArrayList<>(n + 1);
for (int i = 0; i < n + 1; ++i) {
bit.add(sup.get());
}
this.bif = bif;
}
void update(int i, T v) {
for (int x = i; x <= n; x += x & -x) {
bit.set(x, bif.apply(bit.get(x), v));
}
}
T reduce(int i, Supplier<T> sup) {
T ret = sup.get();
for (int x = i; x > 0; x -= x & -x) {
ret = bif.apply(ret, bit.get(x));
}
return ret;
}
}
long MOD = 1_000_000_007;
long pow(long a, long r) {
long sum = 1;
while (r > 0) {
if ((r & 1) == 1) {
sum *= a;
sum %= MOD;
}
a *= a;
a %= MOD;
r >>= 1;
}
return sum;
}
long C(int n, int r) {
long sum = 1;
for (int i = n; 0 < i; --i) {
sum *= i;
sum %= MOD;
}
long s = 1;
for (int i = r; 0 < i; --i) {
s *= i;
s %= MOD;
}
sum *= pow(s, MOD - 2);
sum %= MOD;
long t = 1;
for (int i = n - r; 0 < i; --i) {
t *= i;
t %= MOD;
}
sum *= pow(t, MOD - 2);
sum %= MOD;
return sum;
}
double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;
/**
* 黄金分割探索
*
* @param left 下限
* @param right 上限
* @param f 探索する関数
* @param comp 上に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue)
* 下に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue).reversed()
* @return 極値の座標x
*/
double goldenSectionSearch(double left, double right, Function<Double, Double> f, Comparator<Double> comp) {
double c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
double c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
double d1 = f.apply(c1);
double d2 = f.apply(c2);
while (right - left > 1e-9) {
if (comp.compare(d1, d2) > 0) {
right = c2;
c2 = c1;
d2 = d1;
c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
d1 = f.apply(c1);
} else {
left = c1;
c1 = c2;
d1 = d2;
c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
d2 = f.apply(c2);
}
}
return right;
}
/**
* [a,b]をm:nに内分する点を返す
*/
double divideInternally(double a, double b, double m, double n) {
return (n * a + m * b) / (m + n);
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
public FastScanner(InputStream in) {
this.in = in;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte()) return buffer[ptr++];
else return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private void skipUnprintable() {
while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
}
public boolean hasNext() {
skipUnprintable();
return hasNextByte();
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
}
}
Submission Info
Submission Time |
|
Task |
B - 円錐 |
User |
arukuka |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
100 |
Code Size |
6176 Byte |
Status |
AC |
Exec Time |
296 ms |
Memory |
20636 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
Subtask1 |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt, subtask1_31.txt, subtask1_32.txt, subtask1_33.txt, subtask1_34.txt, subtask1_35.txt, subtask1_36.txt, subtask1_37.txt, subtask1_38.txt, subtask1_39.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
249 ms |
20112 KB |
sample_02.txt |
AC |
242 ms |
19408 KB |
subtask1_01.txt |
AC |
287 ms |
20120 KB |
subtask1_02.txt |
AC |
261 ms |
20020 KB |
subtask1_03.txt |
AC |
280 ms |
19772 KB |
subtask1_04.txt |
AC |
279 ms |
19768 KB |
subtask1_05.txt |
AC |
276 ms |
20124 KB |
subtask1_06.txt |
AC |
274 ms |
20636 KB |
subtask1_07.txt |
AC |
258 ms |
20280 KB |
subtask1_08.txt |
AC |
262 ms |
19868 KB |
subtask1_09.txt |
AC |
273 ms |
20100 KB |
subtask1_10.txt |
AC |
272 ms |
20236 KB |
subtask1_11.txt |
AC |
278 ms |
20016 KB |
subtask1_12.txt |
AC |
271 ms |
20008 KB |
subtask1_13.txt |
AC |
278 ms |
20280 KB |
subtask1_14.txt |
AC |
283 ms |
20512 KB |
subtask1_15.txt |
AC |
285 ms |
20280 KB |
subtask1_16.txt |
AC |
276 ms |
19996 KB |
subtask1_17.txt |
AC |
286 ms |
20400 KB |
subtask1_18.txt |
AC |
286 ms |
19752 KB |
subtask1_19.txt |
AC |
296 ms |
20516 KB |
subtask1_20.txt |
AC |
284 ms |
20380 KB |
subtask1_21.txt |
AC |
276 ms |
20404 KB |
subtask1_22.txt |
AC |
286 ms |
20404 KB |
subtask1_23.txt |
AC |
277 ms |
20412 KB |
subtask1_24.txt |
AC |
276 ms |
20252 KB |
subtask1_25.txt |
AC |
295 ms |
20020 KB |
subtask1_26.txt |
AC |
283 ms |
19776 KB |
subtask1_27.txt |
AC |
288 ms |
19904 KB |
subtask1_28.txt |
AC |
277 ms |
19736 KB |
subtask1_29.txt |
AC |
273 ms |
20276 KB |
subtask1_30.txt |
AC |
295 ms |
20284 KB |
subtask1_31.txt |
AC |
293 ms |
20280 KB |
subtask1_32.txt |
AC |
282 ms |
19764 KB |
subtask1_33.txt |
AC |
278 ms |
20268 KB |
subtask1_34.txt |
AC |
290 ms |
19740 KB |
subtask1_35.txt |
AC |
294 ms |
20248 KB |
subtask1_36.txt |
AC |
286 ms |
20284 KB |
subtask1_37.txt |
AC |
283 ms |
19632 KB |
subtask1_38.txt |
AC |
280 ms |
20160 KB |
subtask1_39.txt |
AC |
275 ms |
20240 KB |