#include <bits/stdc++.h>
#define maxX 100005
#define maxN 100005
using namespace std;
struct pravougaonik{
long long x1,x2,y1,y2;
};
struct cvor{
int x1,x2,y1,y2,val,c1,c2,c3,c4;
};
vector <cvor> cv;
vector <pravougaonik> v;
pravougaonik p;
cvor k;
int n,a,b,i,tmp;
long long ans1,ans2;
void ubaci(int koren,int x,int y){
cvor k=cv[koren];
if(k.x1==k.x2 && k.y1==k.y2) {cv[koren].val=1; return;}
if(x<=(k.x1+k.x2)/2 && y<=(k.y1+k.y2)/2 && k.c1!=-1) {ubaci(k.c1,x,y); return;}
if(x<=(k.x1+k.x2)/2 && y>(k.y1+k.y2)/2 && k.c2!=-1) {ubaci(k.c2,x,y); return;}
if(x>(k.x1+k.x2)/2 && y<=(k.y1+k.y2)/2 && k.c3!=-1) {ubaci(k.c3,x,y); return;}
if(x>(k.x1+k.x2)/2 && y>(k.y1+k.y2)/2 && k.c4!=-1) {ubaci(k.c4,x,y); return;}
cvor c;
//if(x==6) cout<<(k.x1+k.x2)/2<<" "<<(k.y1+k.y2)/2<<endl;
c.c1=c.c2=c.c3=c.c4=-1;
if(x<=(k.x1+k.x2)/2 && y<=(k.y1+k.y2)/2) {c.x1=k.x1; c.y1=k.y1; c.x2=(k.x1+k.x2)/2; c.y2=(k.y1+k.y2)/2; cv[koren].c1=cv.size(); cv.push_back(c); ubaci(cv.size()-1,x,y); return;}
if(x<=(k.x1+k.x2)/2 && y>(k.y1+k.y2)/2) {c.x1=k.x1; c.y2=k.y2; c.x2=(k.x1+k.x2)/2; c.y1=(k.y1+k.y2)/2+1; cv[koren].c2=cv.size(); cv.push_back(c); ubaci(cv.size()-1,x,y); return;}
if(x>(k.x1+k.x2)/2 && y<=(k.y1+k.y2)/2) {c.x2=k.x2; c.y1=k.y1; c.x1=(k.x1+k.x2)/2+1; c.y2=(k.y1+k.y2)/2; cv[koren].c3=cv.size(); cv.push_back(c); ubaci(cv.size()-1,x,y); return;}
if(x>(k.x1+k.x2)/2 && y>(k.y1+k.y2)/2) {c.x2=k.x2; c.y2=k.y2; c.x1=(k.x1+k.x2)/2+1; c.y1=(k.y1+k.y2)/2+1; cv[koren].c4=cv.size(); cv.push_back(c); ubaci(cv.size()-1,x,y); return;}
}
int query(int koren,int x,int y){
cvor k=cv[koren];
//cout<<k.x1<<" "<<k.x2<<" "<<k.y1<<" "<<<<endl;
if(k.x1==k.x2 && k.y1==k.y2) return cv[koren].val;
if(x<=(k.x1+k.x2)/2 && y<=(k.y1+k.y2)/2) return query(k.c1,x,y);
if(x<=(k.x1+k.x2)/2 && y>(k.y1+k.y2)/2) return query(k.c2,x,y);
if(x>(k.x1+k.x2)/2 && y<=(k.y1+k.y2)/2) return query(k.c3,x,y);
if(x>(k.x1+k.x2)/2 && y>(k.y1+k.y2)/2) return query(k.c4,x,y);
}
void update(int koren,int x1,int y1,int x2,int y2,int v){
cvor k=cv[koren];
if(k.x1==k.x2 && k.y1==k.y2) {cv[koren].val=v; return;}
if(x1<=(k.x1+k.x2)/2 && y1<=(k.y1+k.y2)/2 && k.c1!=-1) update(k.c1,x1,y1,x2,y2,v);
if(x1<=(k.x1+k.x2)/2 && y2>(k.y1+k.y2)/2 && k.c2!=-1) update(k.c2,x1,y1,x2,y2,v);
if(x2>(k.x1+k.x2)/2 && y1<=(k.y1+k.y2)/2 && k.c3!=-1) update(k.c3,x1,y1,x2,y2,v);
if(x2>(k.x1+k.x2)/2 && y2>(k.y1+k.y2)/2 && k.c4!=-1) update(k.c4,x1,y1,x2,y2,v);
}
struct upit{
int x,y,d;
};
upit h;
vector <upit> u;
int main()
{
std::ios_base::sync_with_stdio(false);
cin>>a>>b;
v.push_back(p);
p.x1=p.y1=0;
p.x2=a;
p.y2=b;
v.push_back(p);
cin>>n;
k.c1=k.c2=k.c3=k.c4=-1;
k.x1=k.y1=0;
k.x2=a;
k.y2=b;
cv.push_back(k);
for(i=0;i<n;i++){
int x,y,d;
cin>>x>>y>>d;
h.x=x;
h.y=y;
h.d=d;
u.push_back(h);
ubaci(0,x,y);
}
for(i=0;i<n;i++){
int x,y,d;
x=u[i].x;
y=u[i].y;
d=u[i].d;
tmp=query(0,x,y);
if(d==1){
p=v[tmp];
p.y2=y;
v[tmp].y1=y;
v.push_back(p);
ans1=(v[tmp].y2-v[tmp].y1)*(v[tmp].x2-v[tmp].x1);
ans2=(p.y2-p.y1)*(p.x2-p.x1);
if(ans1<=ans2){
swap(v[tmp],v.back());
}
p=v.back();
update(0,p.x1,p.y1,p.x2,p.y2,v.size()-1);
}
else{
p=v[tmp];
p.x2=x;
v[tmp].x1=x;
v.push_back(p);
ans1=(v[tmp].y2-v[tmp].y1)*(v[tmp].x2-v[tmp].x1);
ans2=(p.y2-p.y1)*(p.x2-p.x1);
if(ans1<=ans2){
swap(v[tmp],v.back());
}
p=v.back();
update(0,p.x1,p.y1,p.x2,p.y2,v.size()-1);
}
cout<<min(ans1,ans2)<<" "<<max(ans1,ans2)<<endl;
}
return 0;
}
Compilation message
krave.cpp: In function 'int query(int, int, int)':
krave.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
632 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1116 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1346 ms |
23164 KB |
Output is correct |
| 2 |
Correct |
177 ms |
17060 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1201 ms |
23208 KB |
Output is correct |
| 2 |
Correct |
197 ms |
18912 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1473 ms |
23192 KB |
Output is correct |
| 2 |
Correct |
227 ms |
20576 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
356 ms |
20708 KB |
Output is correct |
| 2 |
Correct |
184 ms |
17012 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
887 ms |
41212 KB |
Output is correct |
| 2 |
Correct |
206 ms |
18652 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
846 ms |
41152 KB |
Output is correct |
| 2 |
Correct |
651 ms |
21280 KB |
Output is correct |
| 3 |
Correct |
226 ms |
19168 KB |
Output is correct |
| 4 |
Correct |
217 ms |
19804 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
780 ms |
41280 KB |
Output is correct |
| 2 |
Correct |
707 ms |
23536 KB |
Output is correct |
| 3 |
Correct |
234 ms |
19380 KB |
Output is correct |
| 4 |
Correct |
230 ms |
20572 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
982 ms |
41024 KB |
Output is correct |
| 2 |
Correct |
429 ms |
20056 KB |
Output is correct |
| 3 |
Correct |
233 ms |
20580 KB |
Output is correct |
| 4 |
Correct |
246 ms |
22620 KB |
Output is correct |
