Submission #1029004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029004		lucri	trapezoid (balkan11_trapezoid)	C++17	36 / 100	115 ms	13516 KiB

trapezoid

#include <bits/stdc++.h>
#define MOD 30013
using namespace std;
struct arboreintervale{int nrmax,fr;}aint[1600010],val[100010],pre;
priority_queue<pair<int,pair<int,int>>>q;
int n,a,b,c,d;
arboreintervale join(arboreintervale a,arboreintervale b)
{
    if(a.nrmax>b.nrmax)
        return a;
    if(a.nrmax<b.nrmax)
        return b;
    return {a.nrmax,a.fr+b.fr};
}
void adauga(int poz,int b,int e,int pozu,arboreintervale val)
{
    if(pozu>e||pozu<b)
        return;
    if(b==e)
    {
        aint[poz]=val;
        return;
    }
    adauga(poz*2,b,(b+e)/2,pozu,val);
    adauga(poz*2+1,(b+e)/2+1,e,pozu,val);
    aint[poz]=join(aint[poz*2],aint[poz*2+1]);
}
void maxim(int poz,int b,int e,int bi,int ei)
{
    if(bi>e||ei<b)
        return;
    if(bi<=b&&e<=ei)
    {
        pre=join(pre,aint[poz]);
        return;
    }
    maxim(poz*2,b,(b+e)/2,bi,ei);
    maxim(poz*2+1,(b+e)/2+1,e,bi,ei);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a>>b>>c>>d;
        q.push({-a,{c,i}});
        q.push({-b,{d,-i}});
    }
    while(!q.empty())
    {
        pre={0,1};
        int a=-q.top().first,b=q.top().second.first,c=q.top().second.second;
        q.pop();
        if(c<0)
            adauga(1,1,400000,b,val[-c]);
        else
        {
            maxim(1,1,400000,1,b);
            ++pre.nrmax;
            val[c]=pre;
        }
    }
    cout<<aint[1].nrmax<<' '<<aint[1].fr;
    return 0;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:52:13: warning: unused variable 'a' [-Wunused-variable]
   52 |         int a=-q.top().first,b=q.top().second.first,c=q.top().second.second;
      |             ^

• Subtask 1: 36 / 100