oj.uz

Submission #1012718

# Submission time Handle Problem Language Result Execution time Memory
1012718 2024-07-02T14:14:26 Z vjudge1 Krave (COI14_krave) C++17
100 / 100
 355 ms 110032 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 19 ms 37976 KB Output is correct
2 Correct 16 ms 37980 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 38352 KB Output is correct
2 Correct 21 ms 38704 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 62984 KB Output is correct
2 Correct 124 ms 62944 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 62764 KB Output is correct
2 Correct 168 ms 69972 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 62800 KB Output is correct
2 Correct 214 ms 78416 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 52048 KB Output is correct
2 Correct 223 ms 81236 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 65616 KB Output is correct
2 Correct 253 ms 87376 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 65012 KB Output is correct
2 Correct 180 ms 75552 KB Output is correct
3 Correct 174 ms 67764 KB Output is correct
4 Correct 311 ms 96084 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 65904 KB Output is correct
2 Correct 201 ms 79440 KB Output is correct
3 Correct 285 ms 105296 KB Output is correct
4 Correct 283 ms 96336 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 65960 KB Output is correct
2 Correct 159 ms 69572 KB Output is correct
3 Correct 310 ms 110032 KB Output is correct
4 Correct 312 ms 95828 KB Output is correct