| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 734144 |
2023-05-01T22:47:33 Z |
Trunkty |
Krave (COI14_krave) |
C++14 |
|
1622 ms |
82664 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
int w,h,n;
set<vector<int>> vert[400020],hori[400020];
void addto(int node, int vl, int vr, int typ){
if(typ==1){
auto it = vert[node].lower_bound({vl,-1});
if(it!=vert[node].end() and (*it)[0]<=vr){
vr = max(vr,(*it)[1]);
vl = min(vl,(*it)[0]);
vert[node].erase(it);
}
it = vert[node].lower_bound({vl,-1});
if(it!=vert[node].begin()){
it--;
if((*it)[1]>=vl){
vr = max(vr,(*it)[1]);
vl = min(vl,(*it)[0]);
vert[node].erase(it);
}
}
//cout << vl << " " << vr << " " << node << "\n";
vert[node].insert({vl,vr});
}
else{
auto it = hori[node].lower_bound({vl,-1});
if(it!=hori[node].end() and (*it)[0]<=vr){
vr = max(vr,(*it)[1]);
vl = min(vl,(*it)[0]);
hori[node].erase(it);
}
it = hori[node].lower_bound({vl,-1});
if(it!=hori[node].begin()){
it--;
if((*it)[1]>=vl){
vr = max(vr,(*it)[1]);
vl = min(vl,(*it)[0]);
hori[node].erase(it);
}
}
hori[node].insert({vl,vr});
}
}
void updatevert(int node, int l, int r, int pos, int vl, int vr){
//cout << node << " " << l << " " << r << "\n";
addto(node,vl,vr,1);
if(l!=r){
int mid = (l+r)/2;
if(pos<=mid){
updatevert(node*2,l,mid,pos,vl,vr);
}
else{
updatevert(node*2+1,mid+1,r,pos,vl,vr);
}
}
}
void updatehori(int node, int l, int r, int pos, int vl, int vr){
addto(node,vl,vr,2);
if(l!=r){
int mid = (l+r)/2;
if(pos<=mid){
updatehori(node*2,l,mid,pos,vl,vr);
}
else{
updatehori(node*2+1,mid+1,r,pos,vl,vr);
}
}
}
bool isin(int node, int c, int typ){
if(typ==1){
auto it = vert[node].lower_bound({c,2000000000});
if(it==vert[node].begin()){
return false;
}
it--;
if((*it)[1]>=c){
return true;
}
else{
return false;
}
}
else{
auto it = hori[node].lower_bound({c,2000000000});
if(it==hori[node].begin()){
return false;
}
it--;
if((*it)[1]>=c){
return true;
}
else{
return false;
}
}
}
int queryvertlef(int node, int l, int r, int needl, int needr, int c){
if(l>needr or r<needl){
return 2e9;
}
else if(l>=needl and r<=needr){
if(isin(node,c,1)){
int mid = (l+r)/2;
if(l==r){
return l;
}
else if(isin(node*2+1,c,1)){
return queryvertlef(node*2+1,mid+1,r,needl,needr,c);
}
else{
return queryvertlef(node*2,l,mid,needl,needr,c);
}
}
else{
return 2e9;
}
}
else{
int mid = (l+r)/2;
int b = queryvertlef(node*2+1,mid+1,r,needl,needr,c);
if(b<2e9){
return b;
}
else{
return queryvertlef(node*2,l,mid,needl,needr,c);
}
}
}
int queryvertrit(int node, int l, int r, int needl, int needr, int c){
if(l>needr or r<needl){
return 2e9;
}
else if(l>=needl and r<=needr){
if(isin(node,c,1)){
int mid = (l+r)/2;
if(l==r){
return l;
}
else if(isin(node*2,c,1)){
return queryvertrit(node*2,l,mid,needl,needr,c);
}
else{
return queryvertrit(node*2+1,mid+1,r,needl,needr,c);
}
}
else{
return 2e9;
}
}
else{
int mid = (l+r)/2;
int a = queryvertrit(node*2,l,mid,needl,needr,c);
if(a<2e9){
return a;
}
else{
return queryvertrit(node*2+1,mid+1,r,needl,needr,c);
}
}
}
int queryhoridow(int node, int l, int r, int needl, int needr, int c){
if(l>needr or r<needl){
return 2e9;
}
else if(l>=needl and r<=needr){
if(isin(node,c,2)){
int mid = (l+r)/2;
if(l==r){
return l;
}
else if(isin(node*2+1,c,2)){
return queryhoridow(node*2+1,mid+1,r,needl,needr,c);
}
else{
return queryhoridow(node*2,l,mid,needl,needr,c);
}
}
else{
return 2e9;
}
}
else{
int mid = (l+r)/2;
int b = queryhoridow(node*2+1,mid+1,r,needl,needr,c);
if(b<2e9){
return b;
}
else{
return queryhoridow(node*2,l,mid,needl,needr,c);
}
}
}
int queryhoriup(int node, int l, int r, int needl, int needr, int c){
if(l>needr or r<needl){
return 2e9;
}
else if(l>=needl and r<=needr){
if(isin(node,c,2)){
int mid = (l+r)/2;
if(l==r){
return l;
}
else if(isin(node*2,c,2)){
return queryhoriup(node*2,l,mid,needl,needr,c);
}
else{
return queryhoriup(node*2+1,mid+1,r,needl,needr,c);
}
}
else{
return 2e9;
}
}
else{
int mid = (l+r)/2;
int a = queryhoriup(node*2,l,mid,needl,needr,c);
if(a<2e9){
return a;
}
else{
return queryhoriup(node*2+1,mid+1,r,needl,needr,c);
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> w >> h >> n;
updatevert(1,0,w,0,0,h);
updatevert(1,0,w,w,0,h);
updatehori(1,0,h,0,0,w);
updatehori(1,0,h,h,0,w);
/*
cout << queryvertlef(1,0,w,0,w,0) << "\n";
cout << queryvertlef(1,0,w,0,w,1) << "\n";
cout << queryvertlef(1,0,w,0,w-1,h) << "\n";
cout << queryhoridow(1,0,h,0,h,0) << "\n";
cout << queryhoridow(1,0,h,0,h,1) << "\n";
cout << queryhoridow(1,0,h,0,h-1,w) << "\n";
*/
for(int i=1;i<=n;i++){
int a,b,c;
cin >> a >> b >> c;
int up=queryhoriup(1,0,h,b,h,a);
int down=queryhoridow(1,0,h,0,b,a);
int lef=queryvertlef(1,0,w,0,a,b);
int rit=queryvertrit(1,0,w,a,w,b);
if(c==1){
cout << min((up-b)*(rit-lef),(b-down)*(rit-lef)) << " " << max((up-b)*(rit-lef),(b-down)*(rit-lef)) << "\n";
updatehori(1,0,h,b,lef,rit);
}
else{
cout << min((up-down)*(rit-a),(up-down)*(a-lef)) << " " << max((up-down)*(rit-a),(up-down)*(a-lef)) << "\n";
updatevert(1,0,w,a,down,up);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
37964 KB |
Output is correct |
| 2 |
Correct |
18 ms |
37832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
38660 KB |
Output is correct |
| 2 |
Correct |
26 ms |
38604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
645 ms |
69136 KB |
Output is correct |
| 2 |
Correct |
384 ms |
53156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
651 ms |
69508 KB |
Output is correct |
| 2 |
Correct |
435 ms |
55244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
675 ms |
69488 KB |
Output is correct |
| 2 |
Correct |
565 ms |
57592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
622 ms |
59284 KB |
Output is correct |
| 2 |
Correct |
372 ms |
59712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1622 ms |
82564 KB |
Output is correct |
| 2 |
Correct |
419 ms |
62816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1565 ms |
79932 KB |
Output is correct |
| 2 |
Correct |
320 ms |
49796 KB |
Output is correct |
| 3 |
Correct |
471 ms |
59440 KB |
Output is correct |
| 4 |
Correct |
464 ms |
64388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1615 ms |
82664 KB |
Output is correct |
| 2 |
Correct |
329 ms |
51248 KB |
Output is correct |
| 3 |
Correct |
491 ms |
59836 KB |
Output is correct |
| 4 |
Correct |
479 ms |
66072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1540 ms |
82584 KB |
Output is correct |
| 2 |
Correct |
300 ms |
50952 KB |
Output is correct |
| 3 |
Correct |
523 ms |
59868 KB |
Output is correct |
| 4 |
Correct |
514 ms |
67524 KB |
Output is correct |
