Submission #1262609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262609		sofija6	trapezoid (balkan11_trapezoid)	C++20	46 / 100	297 ms	54700 KiB

trapezoid

#include <bits/stdc++.h>
#define ll int
#define MAXN 100010
#define MOD 30013
using namespace std;
struct trapezoid
{
    ll a,b,c,d;
};
trapezoid t[MAXN];
bool Cmp(trapezoid x,trapezoid y)
{
    return x.a<y.a;
}
map<ll,ll> val;
ll cnt=1,sz=1;
struct element
{
    ll maxx,num;
};
element Merge(element x,element y)
{
    if (x.maxx>y.maxx)
        return x;
    if (x.maxx<y.maxx)
        return y;
    return {x.maxx,(x.maxx?x.num+y.num : 1)};
}
element neutral={0,1};
struct seg_tree
{
    vector<element> st;
    void Init()
    {
        while (sz<cnt)
            sz <<= 1;
        st.resize(2*sz+2,neutral);
    }
    void Update(ll pos,element val,ll x,ll lx,ll rx)
    {
        if (lx==rx)
        {
            st[x]=Merge(st[x],val);
            return;
        }
        ll mid=(lx+rx)/2;
        if (pos<=mid)
            Update(pos,val,2*x,lx,mid);
        else
            Update(pos,val,2*x+1,mid+1,rx);
        st[x]=Merge(st[2*x],st[2*x+1]);
    }
    element Calc(ll l,ll r,ll x,ll lx,ll rx)
    {
        if (lx>r || rx<l)
            return neutral;
        if (lx>=l && rx<=r)
            return st[x];
        ll mid=(lx+rx)/2;
        return Merge(Calc(l,r,2*x,lx,mid),Calc(l,r,2*x+1,mid+1,rx));
    }
};
element ans[MAXN];
vector<ll> toadd[4*MAXN];
seg_tree S;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    set<ll> s;
    cin >> n;
    for (ll i=1;i<=n;i++)
    {
        cin >> t[i].a >> t[i].b >> t[i].c >> t[i].d;
        s.insert(t[i].a);
        s.insert(t[i].b);
        s.insert(t[i].c);
        s.insert(t[i].d);
    }
    sort(t+1,t+1+n,Cmp);
    for (ll i : s)
        val[i]=cnt++;
    for (ll i=1;i<=n;i++)
    {
        t[i].a=val[t[i].a];
        t[i].b=val[t[i].b];
        t[i].c=val[t[i].c];
        t[i].d=val[t[i].d];
    }
    ll cur=0;
    S.Init();
    for (ll i=1;i<=n;i++)
    {
        while (cur<t[i].a)
        {
            for (ll ind : toadd[cur])
                S.Update(t[ind].d,ans[ind],1,1,sz);
            cur++;
        }
        ans[i]=S.Calc(1,t[i].c,1,1,sz);
        ans[i].maxx++;
        toadd[t[i].b].push_back(i);
    }
    element anss=neutral;
    for (ll i=1;i<=n;i++)
        anss=Merge(anss,ans[i]);
    cout << anss.maxx << " " << anss.num << "\n";
    return 0;
}

• Subtask 1: 46 / 100