Submission #1012717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012717		DucNguyen2007	Krave (COI14_krave)	C++14	100 / 100	390 ms	111496 KiB

krave

#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 / 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