Submission #268436

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
268436	2020-08-16T11:48:27 Z	stefantaga	trapezoid (balkan11_trapezoid)	C++14	100 / 100	348 ms	25080 KB

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;
        if (c.nr>=MOD)
        {
            c.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()
{
    ios  :: sync_with_stdio(false);
    cin.tie(0);
    #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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	2 ms	640 KB	Output is correct
5	Correct	4 ms	896 KB	Output is correct
6	Correct	6 ms	1152 KB	Output is correct
7	Correct	9 ms	1408 KB	Output is correct
8	Correct	12 ms	1664 KB	Output is correct
9	Correct	29 ms	3192 KB	Output is correct
10	Correct	48 ms	5624 KB	Output is correct
11	Correct	65 ms	6904 KB	Output is correct
12	Correct	182 ms	12920 KB	Output is correct
13	Correct	194 ms	15480 KB	Output is correct
14	Correct	267 ms	17788 KB	Output is correct
15	Correct	323 ms	18936 KB	Output is correct
16	Correct	322 ms	20356 KB	Output is correct
17	Correct	340 ms	21424 KB	Output is correct
18	Correct	254 ms	22628 KB	Output is correct
19	Correct	293 ms	23672 KB	Output is correct
20	Correct	348 ms	25080 KB	Output is correct