oj.uz

Submission #1012717

# Submission time Handle Problem Language Result Execution time Memory
1012717 2024-07-02T14:14:03 Z DucNguyen2007 Krave (COI14_krave) C++14
100 / 100
 390 ms 111496 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=1e5+5;
const ll inf=2e18;
ll n,m,q;
struct segment
{
    set<ll> sum[4*maxN+1];
    int l,r,val,pos;
    void Update(int x,int low,int high)
    {
        if(low>r||high<l)
        {
            return;
        }
        if(low>=l&&high<=r)
        {
            sum[x].insert(val);
            return;
        }
        int mid=(low+high)/2;
        Update(2*x,low,mid);
        Update(2*x+1,mid+1,high);
    }
    void update_val(int l,int r,int val)
    {
        this->l=l;
        this->r=r;
        this->val=val;
        Update(1,1,maxN);
    }
    pll meg(pll x,pll y)
    {
        pll res;
        res.fi=max(x.fi,y.fi);
        res.se=min(x.se,y.se);
        return res;
    }
    pll res;
    void get(int x,int low,int high)
    {
        auto it1=sum[x].upper_bound(val);
        auto it2=it1;
        pll p;
        if(sum[x].size()==0)
        {
            p={-inf,inf};
        }
        else
        {
            if(it1==sum[x].begin())
            {
                p={-inf,(*it2)};
            }
            else
            {
                it1--;
                p.fi=(*it1);
                if(it2==sum[x].end())
                {
                    p.se=inf;
                }
                else p.se=(*it2);
            }
        }
        //cout<<x<<" "<<low<<" "<<high<<" "<<p.fi<<" "<<p.se<<" "<<res.fi<<" "<<res.se<<'\n';
        res=meg(res,p);
        if(low==high)
        {
            return;
        }
        int mid=(low+high)/2;
        if(pos<=mid)
        {
            get(2*x,low,mid);
        }
        else get(2*x+1,mid+1,high);
    }
    pll query(int pos,int val)
    {
        this->pos=pos;
        this->val=val;
        res={-inf,inf};
        get(1,1,maxN);
        return res;
    }

}st1,st2;
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>m>>n>>q;
    st1.update_val(1,m,0);
    st1.update_val(1,m,n);
    st2.update_val(1,n,0);
    st2.update_val(1,n,m);
    while(q--)
    {
        ll x,y,d;
        cin>>x>>y>>d;
        pll tmp1=st1.query(x+1,y);
        pll tmp2=st2.query(y+1,x);
        if(d==2)
        {
            ll cur1=(x-tmp2.fi)*(tmp1.se-tmp1.fi);
            ll cur2=(tmp2.se-x)*(tmp1.se-tmp1.fi);
            cout<<min(cur1,cur2)<<" "<<max(cur1,cur2)<<'\n';
            st2.update_val(tmp1.fi+1,tmp1.se,x);
        }
        else
        {
            ll cur1=(y-tmp1.fi)*(tmp2.se-tmp2.fi);
            ll cur2=(tmp1.se-y)*(tmp2.se-tmp2.fi);
            cout<<min(cur1,cur2)<<" "<<max(cur1,cur2)<<'\n';
            st1.update_val(tmp2.fi+1,tmp2.se,y);
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 37980 KB Output is correct
2 Correct 16 ms 37960 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 38492 KB Output is correct
2 Correct 19 ms 38748 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 62916 KB Output is correct
2 Correct 139 ms 63056 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 63060 KB Output is correct
2 Correct 194 ms 70356 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 62960 KB Output is correct
2 Correct 203 ms 78836 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 52048 KB Output is correct
2 Correct 221 ms 82116 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 67140 KB Output is correct
2 Correct 287 ms 88400 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 66228 KB Output is correct
2 Correct 197 ms 76048 KB Output is correct
3 Correct 177 ms 68944 KB Output is correct
4 Correct 329 ms 97360 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 67408 KB Output is correct
2 Correct 237 ms 80160 KB Output is correct
3 Correct 305 ms 106664 KB Output is correct
4 Correct 350 ms 97672 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 67452 KB Output is correct
2 Correct 175 ms 70044 KB Output is correct
3 Correct 295 ms 111496 KB Output is correct
4 Correct 316 ms 97164 KB Output is correct