Submission #268429

#	Time	Username	Problem	Language	Result	Execution time	Memory
268429		stefantaga	trapezoid (balkan11_trapezoid)	C++14	95 / 100	591 ms	27260 KiB

trapezoid

#include <bits/stdc++.h>
#define MOD 30013
using namespace std;
int n,i;
struct wow
{
    int x,y,x2,y2;
}v[100005];
struct arbore
{
    int maxim,nr;
};
arbore aib[200005];
arbore adauga (arbore a,arbore b)
{
    arbore c=a;
    if (c.maxim<b.maxim)
    {
        c.maxim=b.maxim;
        c.nr=0;
    }
    if (c.maxim==b.maxim)
    {
        c.nr=(c.nr+b.nr)%MOD;
    }
    return c;
}
int ub (int x)
{
    return x&(-x);
}
void update (int poz,arbore val)
{
    int i;
    for (i=poz;i<=2*n;i+=ub(i))
    {
        aib[i]=adauga(aib[i],val);
    }
}
arbore query (int poz)
{
    int i;
    arbore suma={0,0};
    for (i=poz;i>=1;i-=ub(i))
    {
       suma= adauga(suma,aib[i]);
    }
    return suma;
}
bool compare (wow a,wow b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
pair <int,int> v2[100005];
int b[100005];
int caut (int val)
{
    int st=1,dr=n,sol=0,mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (val>b[mij])
        {
            sol=mij;
            st=mij+1;
        }
        else
        {
            dr=mij-1;
        }
    }
    return sol;
}
int v3[105],maxim,poz,lung[100005],nr,tip,pozitie;
map <int,int> m1;
map <int,int> m2;
pair <int,int> events[200005];
arbore din[200005],rez;
int main()
{
    #ifdef HOME
    ifstream cin("trapezoid.in");
    ofstream cout("trapezoid.out");
    #endif // HOME
    cin>>n;
    for (i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].x2>>v[i].y2;
        m1[v[i].x]=1;
        m1[v[i].y]=1;
        m2[v[i].x2]=1;
        m2[v[i].y2]=1;
    }
    nr=0;
    for (auto ind : m1)
    {
        nr++;
        m1[ind.first]=nr;
    }
    nr=0;
    for (auto ind : m2)
    {
        nr++;
        m2[ind.first]=nr;
    }
    for (i=1;i<=n;i++)
    {
        v[i].x=m1[v[i].x];
        v[i].y=m1[v[i].y];
        v[i].x2=m2[v[i].x2];
        v[i].y2=m2[v[i].y2];
        events[v[i].x]={i,1};
        events[v[i].y]={i,-1};
    }
    for (i=1;i<=2*n;i++)
    {
        pozitie=events[i].first;
        tip=events[i].second;
        if (tip==1)
        {
            din[pozitie]=query(v[pozitie].x2);
            if (!din[pozitie].nr)
            {
                din[pozitie].nr++;
            }
            din[pozitie].maxim++;
        }
        else
        if (tip==-1)
        {
            update(v[pozitie].y2,din[pozitie]);
        }
    }
    for (i=0;i<=2*n;i++)
    {
        rez=adauga(rez,din[i]);
    }
    cout<<rez.maxim<<" "<<rez.nr<<'\n';
    return 0;
}

• Subtask 1: 95 / 100