Submission #94556

#	Time	Username	Problem	Language	Result	Execution time	Memory
94556		igzi	Krave (COI14_krave)	C++17	100 / 100	1473 ms	41280 KiB

krave

#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 (stderr)

krave.cpp: In function 'int query(int, int, int)':
krave.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12