| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 734143 |
2023-05-01T22:47:03 Z |
Trunkty |
Krave (COI14_krave) |
C++14 |
|
23 ms |
37992 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);
freopen("mondrian.in","r",stdin);
freopen("mondrian.out","w",stdout);
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;
}
Compilation message
krave.cpp: In function 'int main()':
krave.cpp:240:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
240 | freopen("mondrian.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
krave.cpp:241:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
241 | freopen("mondrian.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
37844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
37936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
37968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
37916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
37972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
37868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
37844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
37848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
37876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
37992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
