oj.uz

Submission #94557

# Submission time Handle Problem Language Result Execution time Memory
94557 2019-01-20T16:13:03 Z igzi Krave (COI14_krave) C++17
30 / 100
 5000 ms 40512 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);
            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);
            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 4 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 1156 KB Output is correct
2 Correct 75 ms 1116 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1689 ms 23084 KB Output is correct
2 Execution timed out 5097 ms 11656 KB Time limit exceeded

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1905 ms 23176 KB Output is correct
2 Correct 206 ms 18528 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1908 ms 23108 KB Output is correct
2 Correct 225 ms 19936 KB Output is correct

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 20740 KB Output is correct
2 Execution timed out 5011 ms 11680 KB Time limit exceeded

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 40428 KB Output is correct
2 Execution timed out 5095 ms 12524 KB Time limit exceeded

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 40512 KB Output is correct
2 Execution timed out 5088 ms 20180 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1025 ms 40372 KB Output is correct
2 Execution timed out 5094 ms 20180 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1098 ms 40452 KB Output is correct
2 Execution timed out 5090 ms 20052 KB Time limit exceeded
3 Halted 0 ms 0 KB -