Discussion of Problem 1470. UFOsMain idea is to split cube into 8 parts and query/add for each one. Here is my code that have TL6. Any ideas of how to improve it? import java.io.*; public class P1470 { static int [] tree = new int[10000000]; private static int n; public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out)); n = Integer.valueOf(reader.readLine()); while (true) { String line = reader.readLine(); if (line.startsWith("1")) { add(new Ufo(line)); } else if (line.startsWith("2")){ writer.println(query(new Region(line))); } else { break; } } writer.flush(); } private static int query(Region region) { return doQuery(region, new Region(0, 0, 0, n - 1, n - 1, n - 1), 0); } private static int doQuery(Region q, Region r, int node) { if (!r.overlaps(q)) return 0; if (q.contains(r)) { return tree[node]; } int xMid = (r.x1 + r.x2) / 2; int yMid = (r.y1 + r.y2) / 2; int zMid = (r.z1 + r.z2) / 2; return doQuery(q, new Region(r.x1, r.y1, r.z1, xMid, yMid, zMid), node * 8 + 1) + doQuery(q, new Region(xMid + 1, r.y1, r.z1, r.x2, yMid, zMid), node * 8 + 2) + doQuery(q, new Region(xMid + 1, r.y1, zMid + 1, r.x2, yMid, r.z2), node * 8 + 3) + doQuery(q, new Region(r.x1, r.y1, zMid + 1, xMid, yMid, r.z2), node * 8 + 4) + doQuery(q, new Region(r.x1, yMid + 1, r.z1, xMid, r.y2, zMid), node * 8 + 5) + doQuery(q, new Region(xMid + 1, yMid + 1, r.z1, r.x2, r.y2, zMid), node * 8 + 6) + doQuery(q, new Region(xMid + 1, yMid + 1, zMid + 1, r.x2, r.y2, r.z2), node * 8 + 7) + doQuery(q, new Region(r.x1, yMid + 1, zMid + 1, xMid, r.y2, r.z2), node * 8 + 8); } private static void add(Ufo ufo) { doAdd(ufo, new Region(0, 0, 0, n - 1, n - 1, n - 1), 0); } private static void doAdd(Ufo ufo, Region r, int node) { if (!r.contains(ufo)) return; tree[node] += ufo.count; if (r.isPoint()) return; int xMid = (r.x1 + r.x2) / 2; int yMid = (r.y1 + r.y2) / 2; int zMid = (r.z1 + r.z2) / 2; doAdd(ufo, new Region(r.x1, r.y1, r.z1, xMid, yMid, zMid), node * 8 + 1); doAdd(ufo, new Region(xMid + 1, r.y1, r.z1, r.x2, yMid, zMid), node * 8 + 2); doAdd(ufo, new Region(xMid + 1, r.y1, zMid + 1, r.x2, yMid, r.z2), node * 8 + 3); doAdd(ufo, new Region(r.x1, r.y1, zMid + 1, xMid, yMid, r.z2), node * 8 + 4); doAdd(ufo, new Region(r.x1, yMid + 1, r.z1, xMid, r.y2, zMid), node * 8 + 5); doAdd(ufo, new Region(xMid + 1, yMid + 1, r.z1, r.x2, r.y2, zMid), node * 8 + 6); doAdd(ufo, new Region(xMid + 1, yMid + 1, zMid + 1, r.x2, r.y2, r.z2), node * 8 + 7); doAdd(ufo, new Region(r.x1, yMid + 1, zMid + 1, xMid, r.y2, r.z2), node * 8 + 8); } static class Region { int x1, y1, z1, x2, y2, z2; Region(String s) { String[] split = s.split("\\s"); x1 = Integer.valueOf(split[1]); y1 = Integer.valueOf(split[2]); z1 = Integer.valueOf(split[3]); x2 = Integer.valueOf(split[4]); y2 = Integer.valueOf(split[5]); z2 = Integer.valueOf(split[6]); } Region(int x1, int y1, int z1, int x2, int y2, int z2) { this.x1 = x1; this.y1 = y1; this.z1 = z1; this.x2 = x2; this.y2 = y2; this.z2 = z2; } boolean contains(Ufo ufo) { return ufo.x >= x1 && ufo.x <= x2 && ufo.y >= y1 && ufo.y <= y2 && ufo.z >= z1 && ufo.z <= z2; } boolean contains(Region r) { return overlaps(r) && x1 <= r.x1 && x2 >= r.x2 && y1 <= r.y1 && y2 >= r.y2 && z1 <= r.z1 && z2 >= r.z2; } boolean overlaps(Region r) { return r.x1 <= x2 && r.x2 >= x1 && r.y1 <= y2 && r.y2 >= y1 && r.z1 <= z2 && r.z2 >= z1; } boolean isPoint() { return x1 == x2 && y1 == y2 && z1 == z2; } } static class Ufo { int x, y, z, count; Ufo(String s) { String[] split = s.split("\\s"); x = Integer.valueOf(split[1]); y = Integer.valueOf(split[2]); z = Integer.valueOf(split[3]); count = Integer.valueOf(split[4]); } } } Hi, try searching for Fenwick Tree's in 3 Dimensions. I used template programming to write 3D Fenwick tree and I get "Compiler failed" verdict when compiling with G++ (not "Compilation Error", but "Compiler failed"; no error message). The solution works fine and gets Accepted with Visual Studio and Clang. I assume it is because of the recursive template operations, but it works when I compile it locally with G++ (using the flags provided on help.aspx?topic=cpp). It also work on other online judges, such as codeforces, which also use mingw g++. Could I get some insight on this? I'm curious why this happens. Just write 3d Fenvick Tree. And nothing more. May be you mean "exclusion & inclusion"? Who can give test 2. In some topic was given some and my programm gives right result. why my progam get it??? I think its correct z wrote many tests and all of them my program pass corectly but in test 2 some strange... I know that N in 2 test = 2 if it test from statement? please give me some tests like test #2 here is my code(Fenvick Tree 3D) //code deleted some tests for WA2 3 1 1 1 0 2 1 0 0 0 3 1 0 0 1 3 2 1 1 0 2 2 2 3 answer 2 2 1 0 0 0 10 1 0 0 1 10000 1 0 1 0 50 1 0 1 1 1000 1 1 0 0 5 1 1 0 1 100 1 1 1 0 1 1 1 1 1 127 2 1 1 1 1 1 1 3 answer 127 this tests useful for fenvick tree solution! Edited by author 22.04.2009 20:19 Thanks, second test helped a lot. I've got AC using java in 1 sec with 3D Fenwick tree. Solution can be improved in constant factor if search is done more effectively to avoid duplicate searches while subtracting and adding peaces. Edited by author 17.04.2011 14:39 жаль, но октодерево не проходит по времени. В данной задаче сложность запроса на получения количества НЛО в области - O(N*N) УУУУУУУУУУУУУУУУУУУУУУУх я сдал таки трёхмерным деревом отрезков)))))))))) 390963502:56:55 25 окт 2011 ibra(TNU) 1470. НЛО C++ Accepted 2.73449 976 КБ my simple algo don't fit if compute on each step number of UFO wich belong to sector - its too long (O(n*n)) What's the correct algo for this task? You should use cumulative tables... Octtrees also didn't work! Is there quicker data structure? Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) Help!!! [5] // Problem 1470. UFOs 29 Oct 2007 18:34 I use cumulative tables... But I get TLE 5 =( A[i][j][k][d]=Sum[{i*2^d,j*2^d,k*2^d}:{(i+1)*2^d-1,(j+1)*2^d-1,(k+1)*2^d-1}] I can add the UFO by log(n) time, but the calculation of the total number of UFOs in a sector are too long... =( For example, if N=128 and x1=1, y1=1, z1=1, x2=126, y2=126, z2=126 - my algo gives O(n^2) time... =( My AC program is O((log N)^3) time Mine's too (base4 due to ML). 1.47 sec Hm... My solution uses segment tree in plain array as underlying data structure and it runs in O(n log n) but I've got TLE 6. Probably it's because I've used java and created a lot of objects while processing. Will try to tune performance to fit in time bound. Got the same problem with segment tree and TLE 6, even though I use C++(( Tree Array, like Mobile(IOI2001). Should call'Binary Indexed Tree' Look at this test 2 2 1 1 1 1 1 1 1 0 0 0 1 1 0 1 0 3 2 0 0 0 0 0 0 2 0 0 0 0 1 0 1 0 1 0 -2 2 0 0 0 1 1 1 3 In 6 line we have m=2 but z1>z2. Why??? six integers x1, y1, z1, x2, y2, z2 It has built on my computer successfully. The code is shown below. Help me! --- The code has hidden. Thank you. Hint: Function xxxx(***):***; You'd better not do anything with the result variable before you exit the function. --- Edited by author 26.09.2006 08:09 |
|