結果

問題 No.855 ヘビの日光浴
ユーザー uwiuwi
提出日時 2019-07-26 22:37:29
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 8,811 bytes
コンパイル時間 4,713 ms
コンパイル使用メモリ 89,588 KB
実行使用メモリ 66,560 KB
最終ジャッジ日時 2024-10-01 20:44:19
合計ジャッジ時間 17,465 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
50,576 KB
testcase_01 AC 52 ms
50,428 KB
testcase_02 AC 53 ms
50,528 KB
testcase_03 AC 55 ms
50,668 KB
testcase_04 WA -
testcase_05 AC 51 ms
50,492 KB
testcase_06 AC 52 ms
50,496 KB
testcase_07 AC 52 ms
50,520 KB
testcase_08 AC 53 ms
50,460 KB
testcase_09 WA -
testcase_10 AC 53 ms
50,520 KB
testcase_11 AC 55 ms
50,460 KB
testcase_12 AC 57 ms
50,412 KB
testcase_13 AC 54 ms
50,520 KB
testcase_14 AC 55 ms
50,552 KB
testcase_15 AC 50 ms
50,612 KB
testcase_16 AC 52 ms
50,328 KB
testcase_17 AC 53 ms
50,564 KB
testcase_18 AC 51 ms
50,276 KB
testcase_19 AC 52 ms
50,532 KB
testcase_20 AC 51 ms
50,568 KB
testcase_21 AC 52 ms
50,248 KB
testcase_22 AC 51 ms
50,564 KB
testcase_23 AC 51 ms
50,520 KB
testcase_24 AC 51 ms
50,456 KB
testcase_25 AC 51 ms
50,436 KB
testcase_26 AC 52 ms
50,700 KB
testcase_27 AC 56 ms
50,324 KB
testcase_28 AC 53 ms
50,284 KB
testcase_29 AC 52 ms
50,440 KB
testcase_30 AC 52 ms
50,560 KB
testcase_31 AC 52 ms
50,276 KB
testcase_32 AC 53 ms
50,616 KB
testcase_33 AC 59 ms
50,260 KB
testcase_34 AC 58 ms
50,316 KB
testcase_35 AC 54 ms
50,616 KB
testcase_36 AC 55 ms
50,548 KB
testcase_37 AC 57 ms
50,564 KB
testcase_38 AC 57 ms
50,456 KB
testcase_39 AC 55 ms
50,728 KB
testcase_40 AC 58 ms
50,536 KB
testcase_41 WA -
testcase_42 AC 57 ms
50,476 KB
testcase_43 AC 55 ms
50,400 KB
testcase_44 AC 58 ms
50,184 KB
testcase_45 AC 58 ms
50,128 KB
testcase_46 AC 62 ms
50,188 KB
testcase_47 AC 56 ms
50,520 KB
testcase_48 AC 58 ms
50,528 KB
testcase_49 AC 55 ms
50,572 KB
testcase_50 AC 57 ms
50,320 KB
testcase_51 AC 57 ms
50,392 KB
testcase_52 AC 55 ms
50,580 KB
testcase_53 AC 53 ms
50,576 KB
testcase_54 AC 54 ms
50,084 KB
testcase_55 AC 56 ms
50,284 KB
testcase_56 AC 55 ms
50,280 KB
testcase_57 AC 52 ms
50,564 KB
testcase_58 AC 53 ms
50,536 KB
testcase_59 AC 54 ms
50,356 KB
testcase_60 AC 52 ms
50,580 KB
testcase_61 AC 54 ms
50,544 KB
testcase_62 AC 53 ms
50,528 KB
testcase_63 AC 54 ms
50,632 KB
testcase_64 AC 57 ms
50,552 KB
testcase_65 AC 59 ms
50,324 KB
testcase_66 AC 54 ms
50,564 KB
testcase_67 AC 53 ms
50,588 KB
testcase_68 AC 53 ms
50,556 KB
testcase_69 AC 52 ms
50,468 KB
testcase_70 AC 52 ms
50,504 KB
testcase_71 AC 51 ms
50,324 KB
testcase_72 AC 51 ms
50,564 KB
testcase_73 AC 211 ms
58,496 KB
testcase_74 AC 192 ms
58,632 KB
testcase_75 AC 158 ms
55,392 KB
testcase_76 AC 315 ms
62,128 KB
testcase_77 AC 287 ms
59,936 KB
testcase_78 AC 369 ms
62,008 KB
testcase_79 AC 98 ms
52,304 KB
testcase_80 AC 105 ms
52,408 KB
testcase_81 AC 351 ms
62,868 KB
testcase_82 AC 392 ms
62,224 KB
testcase_83 AC 410 ms
66,484 KB
testcase_84 AC 365 ms
62,220 KB
testcase_85 AC 376 ms
62,188 KB
testcase_86 AC 414 ms
66,560 KB
testcase_87 AC 364 ms
62,136 KB
testcase_88 AC 424 ms
66,392 KB
testcase_89 AC 319 ms
61,456 KB
testcase_90 AC 365 ms
62,244 KB
testcase_91 AC 381 ms
62,236 KB
testcase_92 AC 381 ms
62,216 KB
testcase_93 AC 54 ms
50,528 KB
testcase_94 AC 249 ms
61,284 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package contest190726;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class E {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int H = ni(), W = ni(), n = ni();
int[][] co = new int[n][];
for(int i = 0;i < n;i++) {
co[i] = new int[] {ni(), ni(), ni()};
}
// (0,H+1) 2 (W+1,H+1)
// 1 3
// (0,0) 0 (W+1,0)
int[][] xs = new int[4][];
{
int[] lxs = new int[n];
int p = 0;
for(int i = 0;i < n;i++) {
if(co[i][1] == 0) {
lxs[p++] = co[i][0];
}
}
lxs = Arrays.copyOf(lxs, p);
Arrays.sort(lxs);
xs[0] = uniq(lxs);
}
{
int[] lxs = new int[n];
int p = 0;
for(int i = 0;i < n;i++) {
if(co[i][1] == H+1) {
lxs[p++] = W+1-co[i][0];
}
}
lxs = Arrays.copyOf(lxs, p);
Arrays.sort(lxs);
xs[2] = uniq(lxs);
}
{
int[] lxs = new int[n];
int p = 0;
for(int i = 0;i < n;i++) {
if(co[i][0] == 0) {
lxs[p++] = H+1-co[i][1];
}
}
lxs = Arrays.copyOf(lxs, p);
Arrays.sort(lxs);
xs[1] = uniq(lxs);
}
{
int[] lxs = new int[n];
int p = 0;
for(int i = 0;i < n;i++) {
if(co[i][0] == W+1) {
lxs[p++] = co[i][1];
}
}
lxs = Arrays.copyOf(lxs, p);
Arrays.sort(lxs);
xs[3] = uniq(lxs);
}
SegmentTreeRMQ[] st = new SegmentTreeRMQ[4];
for(int i = 0;i < 4;i++) {
st[i] = new SegmentTreeRMQ(n+1);
}
long ans = 0;
for(int[] c : co) {
int type = 0;
int x = 0;
if(c[1] == 0) {
type = 0;
x = c[0];
}else if(c[0] == 0) {
type = 1;
x = H+1-c[1];
}else if(c[1] == H+1) {
type = 2;
x = W+1-c[0];
}else {
type = 3;
x = c[1];
}
int indx = Arrays.binarySearch(xs[type], x);
int or = -st[type].minx(indx, indx+1);
int y = or + c[2];
int U = type % 2 == 0 ? W+1 : H+1;
int V = type % 2 == 1 ? W+1 : H+1;
int dir = -1;
int minlen = V+1;
{
//
int last = st[type+1&3].lastle(n-1, -x);
if(last != -1) {
int len = V-xs[type+1&3][last];
if(len < minlen) {
minlen = len;
dir = 1;
}
}
}
{
//
int ind = Arrays.binarySearch(xs[type+2&3], U-x);
if(ind >= 0) {
int len = V-(-st[type+2&3].minx(ind, ind+1));
if(len < minlen) {
minlen = len;
dir = 2;
}
}
}
{
//
int first = st[type+3&3].firstle(0, -(U-x));
if(first != -1) {
int len = xs[type+3&3][first];
if(len < minlen) {
minlen = len;
dir = 3;
}
}
}
// tr(minlen, y, dir);
if(minlen <= y) {
//
st[type].update(indx, 0);
ans -= or;
if(dir == -1) {
}else if(dir == 2) {
int ind = Arrays.binarySearch(xs[type+2&3], U-x);
ans -= -st[type+2&3].minx(ind, ind+1);
st[type+2&3].update(ind, 0);
}else if(dir == 1) {
int last = st[type+1&3].lastle(n-1, -x);
ans -= -st[type+1&3].minx(last, last+1);
st[type+1&3].update(last, 0);
}else if(dir == 3) {
int first = st[type+3&3].firstle(0, -(U-x));
ans -= -st[type+3&3].minx(first, first+1);
st[type+3&3].update(first, 0);
}
}else {
st[type].update(Arrays.binarySearch(xs[type], x), -y);
ans += c[2];
}
}
out.println(ans);
}
public static int lowerBound(int[] a, int v){ return lowerBound(a, 0, a.length, v); }
public static int lowerBound(int[] a, int l, int r, int v)
{
if(l > r || l < 0 || r > a.length)throw new IllegalArgumentException();
int low = l-1, high = r;
while(high-low > 1){
int h = high+low>>>1;
if(a[h] >= v){
high = h;
}else{
low = h;
}
}
return high;
}
public static class SegmentTreeRMQ {
public int M, H, N;
public int[] st;
public SegmentTreeRMQ(int n)
{
N = n;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
st = new int[M];
// Arrays.fill(st, 0, M, Integer.MAX_VALUE);
}
public SegmentTreeRMQ(int[] a)
{
N = a.length;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
st = new int[M];
for(int i = 0;i < N;i++){
st[H+i] = a[i];
}
Arrays.fill(st, H+N, M, Integer.MAX_VALUE);
for(int i = H-1;i >= 1;i--)propagate(i);
}
public void update(int pos, int x)
{
st[H+pos] = x;
for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);
}
private void propagate(int i)
{
st[i] = Math.min(st[2*i], st[2*i+1]);
}
public int minx(int l, int r){
int min = Integer.MAX_VALUE;
if(l >= r)return min;
while(l != 0){
int f = l&-l;
if(l+f > r)break;
int v = st[(H+l)/f];
if(v < min)min = v;
l += f;
}
while(l < r){
int f = r&-r;
int v = st[(H+r)/f-1];
if(v < min)min = v;
r -= f;
}
return min;
}
public int min(int l, int r){ return l >= r ? 0 : min(l, r, 0, H, 1);}
private int min(int l, int r, int cl, int cr, int cur)
{
if(l <= cl && cr <= r){
return st[cur];
}else{
int mid = cl+cr>>>1;
int ret = Integer.MAX_VALUE;
if(cl < r && l < mid){
ret = Math.min(ret, min(l, r, cl, mid, 2*cur));
}
if(mid < r && l < cr){
ret = Math.min(ret, min(l, r, mid, cr, 2*cur+1));
}
return ret;
}
}
public int firstle(int l, int v) {
int cur = H+l;
while(true){
if(st[cur] <= v){
if(cur < H){
cur = 2*cur;
}else{
return cur-H;
}
}else{
cur++;
if((cur&cur-1) == 0)return -1;
if((cur&1)==0)cur>>>=1;
}
}
}
public int lastle(int l, int v) {
int cur = H+l;
while(true){
if(st[cur] <= v){
if(cur < H){
cur = 2*cur+1;
}else{
return cur-H;
}
}else{
if((cur&cur-1) == 0)return -1;
cur--;
if((cur&1)==1)cur>>>=1;
}
}
}
}
public static int[] uniq(int[] a)
{
int n = a.length;
int p = 0;
for(int i = 0;i < n;i++) {
if(i == 0 || a[i] != a[i-1])a[p++] = a[i];
}
return Arrays.copyOf(a, p);
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
// Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
// @Override
// public void run() {
// long s = System.currentTimeMillis();
// solve();
// out.flush();
// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
// }
// };
// t.start();
// t.join();
}
public static void main(String[] args) throws Exception { new E().run(); }
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
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;
}
private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[][] nmi(int n, int m) {
int[][] map = new int[n][];
for(int i = 0;i < n;i++)map[i] = na(m);
return map;
}
private int ni() { return (int)nl(); }
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0