Submission #675964

#	Time	Username	Problem	Language	Result	Execution time	Memory
675964		alexdd	trapezoid (balkan11_trapezoid)	C++17	46 / 100	264 ms	31332 KiB

trapezoid

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct event
{
    int tip;///1 - latura stanga
            ///2 - latura dreapta
    int pozs,pozj;
    int index;
};
bool cmp(event x, event y)
{
    return x.pozs < y.pozs;
}
struct node
{
    int mxm;
    int cntm;
};
node combine(node x, node y)
{
    node aux;
    aux.mxm = max(x.mxm,y.mxm);
    aux.cntm=0;
    if(x.mxm == aux.mxm)
        aux.cntm += x.cntm;
    if(y.mxm == aux.mxm)
        aux.cntm += y.cntm;
    return aux;
}
int n;
int a[100001];
int b[100001];
int c[100001];
int d[100001];
vector<event> events;
map<int,int> mp;
map<int,int> nor;
int cntn=0;
int rez[100001];
int cntrez[100001];
void normalizare_c_d()
{
    for(int i=0;i<n;i++)
    {
        mp[c[i]]++;
        mp[d[i]]++;
    }
    int val;
    for(auto it:mp)
    {
        val=it.first;
        cntn++;
        nor[val]=cntn;
    }
    for(int i=0;i<n;i++)
    {
        c[i]=nor[c[i]];
        d[i]=nor[d[i]];
    }
}
node aint[810000];
void upd(int nod, int st, int dr, int poz, node newval)
{
    if(st==dr)
    {
        aint[nod]=newval;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        upd(nod*2,st,mij,poz,newval);
    else
        upd(nod*2+1,mij+1,dr,poz,newval);
    aint[nod]=combine(aint[nod*2],aint[nod*2+1]);
}
node qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return {0,0};
    if(le==st && dr==ri)
        return aint[nod];
    int mij=(st+dr)/2;
    return combine(qry(nod*2,st,mij,le,min(mij,ri)),
                  qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i]>>d[i];
    normalizare_c_d();
    for(int i=0;i<n;i++)
    {
        events.push_back({1,a[i],c[i],i});
        events.push_back({2,b[i],d[i],i});
    }
    sort(events.begin(),events.end(),cmp);
    for(auto e:events)
    {
        if(e.tip==1)
        {
            ///calc rez[e.index]
            ///rez[e.index] = qry max 1..e.pozj-1
            node x = qry(1,1,cntn,1,e.pozj-1);
            rez[e.index] = x.mxm + 1;
            cntrez[e.index] = max(1, x.cntm);
        }
        else
        {
            ///upd aint on position e.pozj with value rez[e.index]
            upd(1,1,cntn,e.pozj,{rez[e.index],cntrez[e.index]});
        }
    }
    int mxmr=0,cntr=0;
    for(int i=0;i<n;i++)
    {
        if(rez[i]>mxmr)
        {
            mxmr=rez[i];
            cntr=cntrez[i];
        }
        else if(rez[i]==mxmr)
            cntr+=cntrez[i];
    }
    cout<<mxmr<<" "<<cntr<<"\n";
    return 0;
}
/**

a     b

c     d

trapezul i poate fi selectat in acelasi timp cu trapezul j daca:
d[j] < c[i]
b[j] < a[i]

avem 2 tipuri de eventuri:
1 - latura stanga
2 - latura dreapta

le sortam dupa pozitia capatului de sus
astfel, reducem a 2-a conditie (b[j] < a[i]), stiind ca ea va fi tot timpul adevarata
ne facem un aint pentru cealalta conditie


*/

• Subtask 1: 46 / 100