oj.uz

Submission #675964

# Submission time Handle Problem Language Result Execution time Memory
675964 2022-12-28T16:32:23 Z alexdd trapezoid (balkan11_trapezoid) C++17
46 / 100
 264 ms 31332 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Partially correct 1 ms 480 KB Partially correct
4 Partially correct 2 ms 596 KB Partially correct
5 Partially correct 5 ms 928 KB Partially correct
6 Partially correct 6 ms 1364 KB Partially correct
7 Partially correct 7 ms 1620 KB Partially correct
8 Partially correct 11 ms 2056 KB Partially correct
9 Partially correct 24 ms 3664 KB Partially correct
10 Partially correct 47 ms 6764 KB Partially correct
11 Partially correct 52 ms 8056 KB Partially correct
12 Partially correct 115 ms 15896 KB Partially correct
13 Partially correct 150 ms 18688 KB Partially correct
14 Partially correct 213 ms 23440 KB Partially correct
15 Partially correct 188 ms 24756 KB Partially correct
16 Partially correct 205 ms 26084 KB Partially correct
17 Partially correct 203 ms 27384 KB Partially correct
18 Partially correct 194 ms 28736 KB Partially correct
19 Partially correct 238 ms 29572 KB Partially correct
20 Partially correct 264 ms 31332 KB Partially correct