oj.uz

Submission #94556

# Submission time Handle Problem Language Result Execution time Memory
94556 2019-01-20T16:12:12 Z igzi Krave (COI14_krave) C++17
100 / 100
 1473 ms 41280 KB 
#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]
 }
 ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1112 KB Output is correct
2 Correct 7 ms 1116 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1346 ms 23164 KB Output is correct
2 Correct 177 ms 17060 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1201 ms 23208 KB Output is correct
2 Correct 197 ms 18912 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1473 ms 23192 KB Output is correct
2 Correct 227 ms 20576 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 20708 KB Output is correct
2 Correct 184 ms 17012 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 887 ms 41212 KB Output is correct
2 Correct 206 ms 18652 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory 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

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory 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

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory 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