I can not find the error. Share the tests, please My solution way getting TLE - on test 32 - while my complexity was O(n ^ 2) I think; but by changing some parameters - coordinates for example - from int to short int, (a 4 byte variable to a 2 byte one) got AC in .3 s. I thought may help you! Good luck :) For N^2 log N solutions. All this can cause you because of antiquicksort test, I think. After I changed sort to stable_sort, everything started to work better. It depends on compiler also. On USACO I had RE #4. New timelimit is 0.5 seconds. All solutions were rejudged. Hi all, i've used segment tree to solve this problem and got stuck with TLE 11. Maybe someone have idea of how to improve this solution to fit in time. Or one can provide test data that will get TLE locally. import java.util.Scanner; public class P1147 { private static final int MAX_COLORS = 2501; private static final short UNKNOWN = 0; private static long c[] = new long[MAX_COLORS]; private static final int TREE_SIZE = 1<<22; private static final int PARTITION_FACTOR = 10; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); short a = scanner.nextShort(); short b = scanner.nextShort(); short n = scanner.nextShort(); short[] tree = new short[TREE_SIZE]; Rectangle[] rectangles = new Rectangle[n + 1]; rectangles[0] = new Rectangle(0, 0, a, b, 1); for (short i = 1; i <= n; i++) { rectangles[i] = new Rectangle(scanner.nextShort(), scanner.nextShort(), scanner.nextShort(), scanner.nextShort(), scanner.nextShort()); } for (double iPartition = 0; iPartition < PARTITION_FACTOR - 1e-6; iPartition++) { for (double jPartition = 0; jPartition < PARTITION_FACTOR - 1e-6; jPartition++) { Rectangle partition = new Rectangle((int) (a * (iPartition / PARTITION_FACTOR)), (int) (b * (jPartition / PARTITION_FACTOR)), (int) (a * ((iPartition + 1) / PARTITION_FACTOR)), (int) (b * ((jPartition + 1) / PARTITION_FACTOR))); for (Rectangle rectangle : rectangles) { insert(tree, 0, rectangle, partition); } countColors(tree, 0, partition); } } for (int i = 0; i < MAX_COLORS; i++) { if (c[i] != 0) { System.out.println(i + " " + c[i]); } } } static void insert(short[] tree, int node, Rectangle rect, Rectangle region) { if (!rect.intersects(region) || !rect.isValid() || !region.isValid()) return; if (rect.contains(region)) { tree[node] = rect.color; } else { if (tree[node] == UNKNOWN) { int xMid = (region.x1 + region.x2) / 2; int yMid = (region.y1 + region.y2) / 2; insert(tree, node * 4 + 1, rect, new Rectangle(region.x1, region.y1, xMid, yMid)); insert(tree, node * 4 + 2, rect, new Rectangle(xMid, region.y1, region.x2, yMid)); insert(tree, node * 4 + 3, rect, new Rectangle(xMid, yMid, region.x2, region.y2)); insert(tree, node * 4 + 4, rect, new Rectangle(region.x1, yMid, xMid, region.y2)); } else { if (tree[node] == rect.color) return; Rectangle bottom = new Rectangle(region.x1, region.y1, region.x2, rect.y1, tree[node]); Rectangle top = new Rectangle(region.x1, rect.y2, region.x2, region.y2, tree[node]); Rectangle left = new Rectangle(region.x1, rect.y1, rect.x1, rect.y2, tree[node]); Rectangle right = new Rectangle(rect.x2, rect.y1, region.x2, rect.y2, tree[node]); tree[node] = UNKNOWN; insert(tree, node, rect, region); insert(tree, node, bottom, region); insert(tree, node, top, region); insert(tree, node, left, region); insert(tree, node, right, region);
} } private static void countColors(short[] tree, int node, Rectangle region) { if (!region.isValid()) return; if (node >= TREE_SIZE) return; if (tree[node] != UNKNOWN) { c[tree[node]] += region.area(); } else { int xMid = (region.x1 + region.x2) / 2; int yMid = (region.y1 + region.y2) / 2; countColors(tree, node * 4 + 1, new Rectangle(region.x1, region.y1, xMid, yMid)); countColors(tree, node * 4 + 2, new Rectangle(xMid, region.y1, region.x2, yMid)); countColors(tree, node * 4 + 3, new Rectangle(xMid, yMid, region.x2, region.y2)); countColors(tree, node * 4 + 4, new Rectangle(region.x1, yMid, xMid, region.y2)); } } static class Rectangle { short x1, y1, x2, y2, color; Rectangle(int x1, int y1, int x2, int y2, int color) { this.x1 = (short) x1; this.y1 = (short) y1; this.x2 = (short) x2; this.y2 = (short) y2; this.color = (short) color; } public Rectangle(int x1, int y1, int x2, int y2) { this(x1, y1, x2, y2, UNKNOWN); } boolean intersects(Rectangle other) { return other.x1 < this.x2 && other.x2 > this.x1 && other.y1 < this.y2 && other.y2 > this.y1; } boolean contains(Rectangle other) { return (other.x1 >= this.x1) && (other.x2 <= this.x2) && (other.y1 >= this.y1) && (other.y2 <= this.y2); } boolean isValid() { return x1 < x2 && y1 < y2; } long area() { return (x2 - x1) * (y2 - y1); } } } Many thanks, Vitaliy first i use RB tree (set in C++) and got AC in 0.796s and when i use heap i AC in 0.156s. my algo is (n^2* log(n)). GOOD LUCK!!! this my code: import java.io.*; import java.util.*; public class Problem_1147 implements Runnable{ public static void main(String []args){ new Thread(new Problem_1147()).start(); } public void run(){ try{ reader = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); //reader = new StreamTokenizer(new BufferedReader(new FileReader("card.out"))); //out = new PrintWriter(new FileWriter("card.out")); solve(); }catch(IOException e){ throw new IllegalStateException(e); } }
final int COLOR_COUNT = 5501; final int N = 400001; int n; int width; int height;
int xPos[] = new int[10001]; int yPos[] = new int[10001];
int color[] = new int[COLOR_COUNT]; int x[] = new int[1001]; int y[] = new int[1001]; int z[] = new int[1001]; int t[] = new int[1001]; int cc[] = new int[1001]; int xc[] = new int[1009]; int yc[] = new int[1009];
short tColor[][] = new short[2002][2002];
StreamTokenizer reader;
PrintWriter out;
int nextInt()throws IOException{ reader.nextToken(); return(int)reader.nval;
}
void solve()throws IOException{
width = nextInt(); height = nextInt(); n = nextInt();
for (int i = 1; i<=n;i++){ x[i] = nextInt(); y[i] = nextInt(); z[i] = nextInt(); t[i] = nextInt();
cc[i] = nextInt(); } x[0] = 0; y[0] = 0; z[0] = width; t[0] = height; cc[0] = 1;
Arrays.fill(xPos,0); Arrays.fill(yPos,0);
for (int i = 0;i <=n ;i++)xPos[x[i]] = xPos[z[i]] = yPos[y[i]] = yPos[t[i]] = 1;
for (int i = 1; i<= width; i++)xPos[i] += xPos[i-1]; for (int i = 1; i<= height; i++)yPos[i] += yPos[i-1];
for (int i = width; i >= 0 ; i-- ) xc[xPos[i]] = i ; for (int i = height; i>= 0 ; i-- ) yc[yPos[i]] = i ;
/* System.out.println("x coords "); for (int i = xPos[0] ; i<=xPos[width];i++)System.out.println(xc[i]); System.out.println("y coords "); for (int i = yPos[0] ; i<=yPos[height];i++)System.out.println(yc[i]); */ for (int i = 0; i<=n;i++){ int i_x = xPos[x[i]]; int j_x = xPos[z[i]]; int i_y = yPos[y[i]]; int j_y = yPos[t[i]]; short c = (short)cc[i]; // System.out.println(i_x +" " +j_x+" " +i_y+" " +j_y); for (int v = i_x; v < j_x; v++){ for (int w = i_y; w < j_y; w++){ tColor[v][w] = c; } } }
Arrays.fill(color, 0); for (int i = xPos[0]; i < xPos[width]; i++){ for (int j = yPos[0]; j < yPos[height]; j++){ color[tColor[i][j]] += (xc[i+1] - xc[i])*(yc[j+1] - yc[j]); } }
for (int i = 1; i<=2500;i++)if (color[i]>0)System.out.println(i+ " "+color[i]); }
} This is my "var"
const big=3000; var i,j,k,l,m,n,l1,l2,now,sum,res,last:longint; f:array[1..big,1..2000]of integer; ans:array[1..2500]of longint; a:array[1..2000]of record x1,y1,x2,y2,col:longint; end; x:array[1..2,0..2000]of longint; mi:array[1..2,0..10000]of longint;
I think I only use about 12MB memory,but the system told me that I got MLE on test 1. Why?Why? sizeof f=24 mb Yeah,I should use smallint Help! Thanks. Edited by author 09.06.2006 18:06 I had WA7 with some old stupid solution which ran through all previous rects and split them apart. Just rewrote it with N^2*log(N) and got AC. I think that 17th test just produces too many pieces for that straight algo to work. It seems like the limits for input values given in problem statement are incorrect - after changing data types from short int (which have max value larger than 30000) to int I got AC for test cases 2..16 - in opposite to the version before this change. So the WA was caused by numbers at input larger than 30000 - it shouldn't happen. Am I wrong or should it be fixed? What about product of these numbers? I tried Quadro and RD Trees and others complicated structures, but failed How it can be? With such various methods author has TLE, I got AC 0.9c with O(N*N*lgn) and interval tree but many authors have 0.001c AC on the same tests? I scan per-row, tracking topmos rectangle in a heap. X coordinates can be sorted only once (then just skip rectangles outside of the current slice) - this improved time from 0.75 sec to 0.28 sec Edited by author 12.08.2008 23:37 I use O(n*n*logn)to AC, too. And my algo can improve to O(nlogn). I make y coordinate as an Interval tree. In my O(n*n*logn) algo,Insert the interval into the tree when x coordinate is different is independent,so it need n time for searching in different x. In fact, the x coordinate which is nearby may be dependent,so we don't have to insert some intervals once more. There are O(n) intervals, each of them just inserts and deletes one time,so it is total up to O(nlogn). Sorry for my bad English. 1003 1003 1000 1 2 1002 3 2 2 1 3 1002 3 1 4 1002 5 2 4 1 5 1002 3 1 6 1002 7 2 6 1 7 1002 3 1 8 1002 9 2 8 1 9 1002 3 ... 1 992 1002 993 2 992 1 993 1002 3 1 994 1002 995 2 994 1 995 1002 3 1 996 1002 997 2 996 1 997 1002 3 1 998 1002 999 2 998 1 999 1002 3 1 1000 1002 1001 2 1000 1 1001 1002 3 This test was in previous subject, but I don't know the correct answer! Mine is: 1 165320 2 34966 3 34214 P. S. I have WA#17 with no thoughts! Thanks. see hint 1003*1003=1006009 165320+34966+34214=234500 undestand when Wrong? 1 256009 2 375000 3 375000 P.S. maybe or 1 252009 2 377000 3 377000 Yeah... I think it wasn't me sending that question! Thanks, I'll work. the correct answer : 1 255009 2 375250 3 375750 Can you give me an expaination that it's clear? I means which is X and wich is Y? A is x and B is y. it means that the upper right coordinate =(A,B). Hi, I just passed Tests of USACO, and then I saw this beautiful solution in "Analysis".Then I tried to implement it. But then I got TLE on test #17 ( in USACO, I submitted this sol, and it runs 10 times faster than N^2logN ). I'm wondering, if this Algo is N^3 . Is it true ? (Sorry for my bad English :p ) Hier is the code : //TLE : #17 acm ru, but 10 times faster in USACO (in comparasion to Heap Algo) #include <iostream> #include <vector> using namespace std; #define FOR(i,n) for(int i=0;i<n;i++) #define CLEAR(A) memset(A,0,sizeof(A)) #define FILL(A,v) fill(A.begin(),A.end(),v) const int maxn = 1002; const int maxC = 2502; class Rect { public: int x1,y1,x2,y2,c; Rect() {} Rect(int xx1,int yy1,int xx2,int yy2,int cc) { x1=xx1;x2=xx2;y1=yy1;y2=yy2;c=cc; } }; vector<int> area(maxC); int N; vector<Rect> rect(0); void Partition(int id,Rect R) { if (R.x1 >= R.x2 || R.y1 >= R.y2 ) return; if (id > N ) { area[R.c] += (R.x2-R.x1)*(R.y2-R.y1); return; } if (R.x1 >= rect[id].x2 || R.x2 <= rect[id].x1 || R.y1 >= rect[id].y2 || R.y2 <= rect[id].y1) Partition(id+1,R); else{ if (rect[id].x2 < R.x2 ) Partition(id+1,Rect(rect[id].x2,R.y1,R.x2,R.y2,R.c)); if (rect[id].x1 > R.x1 ) Partition(id+1,Rect(R.x1,R.y1,rect[id].x1,R.y2,R.c)); if (rect[id].y1 > R.y1 ) Partition(id+1,Rect(max(R.x1,rect[id].x1),R.y1,min(R.x2,rect[id].x2),rect[id].y1,R.c)); if (rect[id].y2 < R.y2 ) Partition(id+1,Rect(max(R.x1,rect[id].x1),rect[id].y2,min(R.x2,rect[id].x2),R.y2,R.c)); } } int main() { FILL(area,0); int A,B,x1,y1,x2,y2,c; cin>> A >> B >> N; rect.resize(N+1); rect[0] = Rect(0,0,A,B,1); for(int i=1;i<=N;i++) { cin>>x1>>y1>>x2>>y2>>c; rect[i]=Rect(x1,y1,x2,y2,c); } for(int i=0;i<=N;i++) Partition(i+1,rect[i]); for(int i=1;i<maxC;i++) if (area[i] > 0) cout<<i<<" "<<area[i]<<endl; return 0; } Tests from USACO are weak. This solution is really O(N^3). Try this test: 1003 1003 1000 1 2 1002 3 2 2 1 3 1002 3 1 4 1002 5 2 4 1 5 1002 3 1 6 1002 7 2 6 1 7 1002 3 ... 1 998 1002 999 2 998 1 999 1002 3 1 1000 1002 1001 2 1000 1 1001 1002 3 Vladimir I cheating avoid test 17 add this test to stop me 1003 1003 1000 1003 1003 1 1 2 1002 3 2 2 1 3 1002 3 1 4 1002 5 2 4 1 5 1002 3 1 6 1002 7 2 6 1 7 1002 3 ... 1 998 1002 999 2 998 1 999 1002 3 1 1000 1002 1001 2 ID of my submit 1225870 Hi! I have AC at USACO, nut here I have WA#17... What's wrong? Thanks Edited by author 03.06.2006 18:19 New tests are harder. Only O(n n log n) solutions and better will work now. Problem was rejudged. add this test please 10 10 5 5 5 6 9 12 3 1 5 7 16 3 2 6 4 33 0 1 6 8 6 0 7 4 9 28 My AC out 1 54 6 38 12 1 28 8 54+38+1+8=101 (100% incorect) correct out 1 53 6 38 12 1 28 8 53+38+1+8=100 ok. I am glad to cooperate. If someone has a better solution, would you please write it down? Thanks. I don`t no how u did.. but maybe you did it in exact O(n^2). I got AC too. and it seemed to be O(n^3), but it was O(n^2) always. I think it is such a good prob... Use 2D interval tree, just O(nlog2n) That`s good... O(n lg^2 n) algorithm using binary tree.... hmm.. it was tough work for me to make program for it.;( I think O(nlgn) is enough, not O(nlg^2n)... And the most important thing is that O(nlogn) algo can save a lot of memory...also, it is faster...:) 2D interval tree uses O(nlg^2)... Now I have a better way, it uses 1D interval tree I think O(nlgn) is enough, not O(nlg^2n)... And the most important thing is that O(nlogn) algo can save a lot of memory...also, it is faster...:) Edited by author 16.06.2005 07:45 program ural1147; const maxn=1000; maxc=2500; type pointer=^node; node=record l,r,b,t,c:word; lb,rb,lt,rt:pointer; end; var x1,y1,x2,y2,color:array[0..maxn]of word; lx,ly:array[0..maxn*2+2]of word; area:array[1..maxc]of longint; n,i,t:word; root:pointer; procedure qsort(var a:array of word;s,t:word); var p,i,j,tmp:word; begin if s>=t then exit; p:=s+random(t-s+1); tmp:=a[p];a[p]:=a[s]; i:=s;j:=t; repeat while (i<j) and (a[j]>=tmp) do dec(j); if i=j then break;a[i]:=a[j];inc(i); while (i<j) and (a[i]<=tmp) do inc(i); if i=j then break;a[j]:=a[i];dec(j); until i=j; a[i]:=tmp; qsort(a,s,i-1); qsort(a,i+1,t); end; procedure makelines(var a,b,l:array of word); var i:word; begin for i:=0 to n do begin l[i*2+1]:=a[i];l[i*2+2]:=b[i]; end; qsort(l,1,n*2+2); l[0]:=1; for i:=2 to n*2+2 do if l[i]>l[i-1] then begin inc(l[0]); l[l[0]]:=l[i]; end; end; function search(l:array of word;x:word):word; var s,t,m:word; begin s:=1;t:=l[0]; repeat m:=(s+t) shr 1; if l[m]=x then break; if l[m]<x then s:=m+1 else t:=m-1; until false; search:=m; end; function min(a,b:word):word; begin if a<b then min:=a else min:=b; end; function max(a,b:word):word; begin if a>b then max:=a else max:=b; end; procedure recycle(p:pointer); begin if p=nil then exit; recycle(p^.lb);recycle(p^.rb);recycle(p^.lt);recycle(p^.rt); dispose(p); end; procedure cover(p:pointer;sx,tx,sy,ty,clr:word); var mx,my:word; begin if (sx>=tx) or (sy>=ty) then exit; if p^.c=clr then exit; if (sx=p^.l) and (tx=p^.r) and (sy=p^.b) and (ty=p^.t) then begin p^.c:=clr; recycle(p^.lb);recycle(p^.rb);recycle(p^.lt);recycle(p^.rt); with p^ do begin lb:=nil;rb:=nil;lt:=nil;rt:=nil;end; exit; end; mx:=(p^.l+p^.r) shr 1;my:=(p^.b+p^.t) shr 1; if p^.c>0 then begin new(p^.lb);with p^.lb^ do begin l:=p^.l;r:=mx;b:=p^.b;t:=my;c:=p^.c;lb:=nil;rb:=nil;lt:=nil;rt:=nil;end; new(p^.rb);with p^.rb^ do begin l:=mx;r:=p^.r;b:=p^.b;t:=my;c:=p^.c;lb:=nil;rb:=nil;lt:=nil;rt:=nil;end; new(p^.lt);with p^.lt^ do begin l:=p^.l;r:=mx;b:=my;t:=p^.t;c:=p^.c;lb:=nil;rb:=nil;lt:=nil;rt:=nil;end; new(p^.rt);with p^.rt^ do begin l:=mx;r:=p^.r;b:=my;t:=p^.t;c:=p^.c;lb:=nil;rb:=nil;lt:=nil;rt:=nil;end; p^.c:=0; end; cover(p^.lb,sx,min(mx,tx),sy,min(my,ty),clr); cover(p^.rb,max(mx,sx),tx,sy,min(my,ty),clr); cover(p^.lt,sx,min(mx,tx),max(my,sy),ty,clr); cover(p^.rt,max(mx,sx),tx,max(my,sy),ty,clr); end; procedure stat(p:pointer); begin if p^.c>0 then inc(area[p^.c],(lx[p^.r]-lx[p^.l])*(ly[p^.t]-ly[p^.b])) else begin stat(p^.lb);stat(p^.rb);stat(p^.lt);stat(p^.rt); end; end; begin x1[0]:=0;y1[0]:=0;read(x2[0],y2[0],n); for i:=1 to n do read(x1[i],y1[i],x2[i],y2[i],color[i]); makelines(x1,x2,lx); makelines(y1,y2,ly); new(root); with root^ do begin l:=1;r:=lx[0];b:=1;t:=ly[0];c:=1; lb:=nil;rb:=nil;lt:=nil;rt:=nil; end; for i:=1 to n do cover(root,search(lx,x1[i]),search(lx,x2[i]),search(ly,y1[i]),search(ly,y2[i]),color[i]); fillchar(area,sizeof(area),0); stat(root); for i:=1 to maxc do if area[i]>0 then writeln(i,' ',area[i]); end. You just have to remember the visible rectangles, for every rectangle go through the list of visible rectangles and determine the intersection of every visible with current rectangle. At the end just count the colours of the visible rectangles. This is n^3 in general, but almost n^2 in average case. And it is not that complicated like your sollution, you just need to compute 16 ways of reletive positions of two rectangles... For each base rectangle -- O(n) For each rectangle covering the base one -- O(n) For storing and calculating the intersection -- O(n log n), I think. I wonder how u can do it in O(n) time? My algorithm in details: I use two arrays of rectangles, visible before adding new rectangle and visible after adding it. At the beginning "before" array is empty. Rectangles are sorted from bottom to top so: for every rectangle CURRENT in input array do for every rectangle R in "before" array compute the intersection with CURRENT and place visible parts of R in "after" array at the end place CURRENT in "after" array "before" array becomes "after" array proceed to next rectangle
Hope this was clear enough, if not I can send you my code. I've done intersection with lots of ifs, for every of the 16 cases. Your algo is really fantastic. I got AC with 0.046s and 485KB. All other complicated stuctures and algoes fail -- like 4-forked trees, like scanning lines -- they get either TLE or MLE, even the standard prog on USACO. The simplest is sometimes the best. But you've made a little mistake -- there are 17 cases, not 16. ....................* ..................... ..................*.. ..................... ................*.... ..................... ..............*...... ..................... ............*........ ..................... ..........*.......... ..................... ........*............ ..................... ......*.............. ..................... ....*................ ..................... ..*.................. ..................... *.................... Each * stands for a small rect. I think this test can make you TLE. THERE IS EXACT N^2 Solution... and it is easy. and (N (lg N)^2) will also get ac. For ~2 of the testcases (on USACO training for same problem), I get a weird overlap, and my area for one of the colours is a bit bigger than that of the real output. Can anyone tell me where my mistake is? Here's my algorithm, which basically reads in the rectangles and is supposed to go back through existing rectangles and reshape them so that there is no overlap. ---------------------------------------------- #include <fstream.h> #include <stdlib.h> struct rect { int x1; int y1; int x2; int y2; int c; bool v; }; int main() { rect sheets[10001]; rect cur; int curTotal = 0; int A, B, N; //A = horizontal, B = vertical fstream infile, outfile; infile.open("rect1.in", ios::in); outfile.open("rect1.out", ios::out); infile >> A >> B >> N; sheets[0].x1 = 0; sheets[0].x2 = A; sheets[0].y1 = 0; sheets[0].y2 = B; sheets[0].c = 1; sheets[0].v = true; curTotal++; for (int i = 0; i < N; i++) { infile >> cur.x1 >> cur.y1 >> cur.x2 >> cur.y2 >> cur.c; //cout << cur.x1 << ' ' << cur.y1 << ' ' << cur.x2 << ' ' << cur.x2 << ' ' << cur.c << endl; for (int j = 0; j < curTotal; j++) { if (!sheets[j].v) continue; //check for simple cases(i.e intersect at a side) if (sheets[j].x1 < cur.x1 && sheets[j].x2 > cur.x1 && sheets[j].x2 <= cur.x2 && sheets[j].y1 >= cur.y1 && sheets[j].y2 <= cur.y2) { sheets[j].x2 = cur.x1; continue; } if (sheets[j].y1 < cur.y1 && sheets[j].y2 > cur.y1 && sheets[j].y2 <= cur.y2 && sheets[j].x1 >= cur.x1 && sheets[j].x2 <= cur.x2) { sheets[j].y2 = cur.y1; continue; } if (sheets[j].x2 > cur.x2 && sheets[j].x1 < cur.x2 && sheets[j].x1 >= cur.x1 && sheets[j].y1 >= cur.y1 && sheets[j].y2 <= cur.y2) { sheets[j].x1 = cur.x2; continue; } if (sheets[j].y2 > cur.y2 && sheets[j].y1 < cur.y2 && sheets[j].y1 >= cur.y1 && sheets[j].x1 >= cur.x1 && sheets[j].x2 <= cur.x2) { sheets[j].y1 = cur.y2; continue; } //check for intersections at corners //upper left corner if (sheets[j].x1 < cur.x1 && sheets[j].x2 > cur.x1 && sheets[j].y1 < cur.y1 && sheets[j].y2 > cur.y1 /*&& sheets[j].y2 < cur.y2*/) { sheets[curTotal].x1 = cur.x1; sheets[curTotal].y1 = sheets[j].y1; sheets[curTotal].x2 = sheets[j].x2; sheets [curTotal].y2 = sheets[j].y2; sheets[curTotal].c = sheets[j].c; sheets [curTotal].v = true; curTotal++; sheets[j].x2 = cur.x1; continue; } //upper right corner if (sheets[j].x2 > cur.x2 && sheets[j].x1 < cur.x2 && sheets[j].y1 < cur.y1 && sheets[j].y2 > cur.y1 /*&& sheets[j].y2 < cur.y2*/) hi pal! i made my own algorithm for USACO and it makes 10 of 11 tests! these 10 tests are easy up to 1000x1000 but in the last there is the maximal data "10000 10000 1000" it's pretty cool!!! so i cheat a bit and i saw the output and then submit it back. got AC and when i so the SOLN my algorithm is good but not for huge tests over 1000x1000 and the code that fits uses the same method like yours. i don't have patience to correct sources! if you want the working code e-mail me and i'll send it to you! deal? zahari, bulgaria Zahari can you give then working sorce from USACO,because i can't solve this problem from several months and i need this sorce.Please send me it to iliyan88@abv.bg |
|