Submission #1029012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029012		lucri	trapezoid (balkan11_trapezoid)	C++17	100 / 100	152 ms	21616 KiB

trapezoid

#include <bits/stdc++.h>
#define MOD 30013
using namespace std;
struct arboreintervale{int nrmax,fr;}aint[800010],val[100010],pre;
priority_queue<pair<int,pair<int,int>>>q;
int n,a[100010],b[100010],c[100010],d[100010],e[200010];
arboreintervale join(arboreintervale a,arboreintervale b)
{
    if(a.nrmax>b.nrmax)
        return a;
    if(a.nrmax<b.nrmax)
        return b;
    if(a.fr+b.fr>=MOD)
        return {a.nrmax,a.fr+b.fr-MOD};
    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);
}
unordered_map<int,int>cod;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        e[2*i-1]=c[i];
        e[2*i]=d[i];
    }
    std::sort(e+1,e+2*n+1);
    for(int i=1;i<=2*n;++i)
        cod[e[i]]=i;
    for(int i=1;i<=n;++i)
    {
        c[i]=cod[c[i]];
        d[i]=cod[d[i]];
        q.push({-a[i],{c[i],i}});
        q.push({-b[i],{d[i],-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,2*n,b,val[-c]);
        else
        {
            maxim(1,1,2*n,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:65:13: warning: unused variable 'a' [-Wunused-variable]
   65 |         int a=-q.top().first,b=q.top().second.first,c=q.top().second.second;
      |             ^

• Subtask 1: 100 / 100