제출 #1129655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129655		I_FloPPed21	사다리꼴 (balkan11_trapezoid)	C++20	12 / 100	490 ms	36852 KiB

trapezoid

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
const long long N=2e5+1;
map<long long,long long>mp;
struct trapezoid
{
    long long a,b,c,d;
} v[N];
long long n,cnt;
vector<long long>buffer;
void change(long long i)
{
    v[i].a=mp[v[i].a];
    v[i].b=mp[v[i].b];
    v[i].c=mp[v[i].c];
    v[i].d=mp[v[i].d];
}
void norm()
{
    sort(buffer.begin(),buffer.end());
    for(auto u:buffer)
    {
        if(mp[u]==0)
        {
            cnt++;
            mp[u]=cnt;
        }
    }
    for(long long i=1; i<=n; i++)
        change(i);
    buffer.clear();
    mp.clear();
}
long long dp[N];//cea mai lunga secventa op care se termina aci;
long long aib[4*N];
void update(long long poz,long long val)
{
    for(long long i=poz; i<=4*n; i+=(i&-i))
    {
        aib[i]=max(aib[i],val);
    }
}
long long query(long long poz)
{
    long long maxx=0;
    for(long long i=poz; i>0; i-=(i&-i))
        maxx=max(maxx,aib[i]);
    return maxx;
}
void clean_aib()
{
    for(long long i=1; i<=4*n; i++)
        aib[i]=0;
}
const long long mod=30013;
long long dp2[N];
void sum_aib(long long poz,long long val)
{
    for(long long i=poz; i<=4*n; i+=(i&-i))
    {
        aib[i]+=val;
        if(aib[i]>=mod)
            aib[i]-=mod;
    }
}
vector<long long>adj[N];
long long query_sum(long long poz)
{
    long long sum=0;
    for(long long i=poz; i>0; i-=(i&-i))
    {
        sum+=aib[i];
        if(sum>=mod)
            sum-=mod;
    }
    return sum;
}
void calculate(long long necesar)
{
    vector<long long>a;
    for(auto u:adj[necesar])
        a.push_back(u);
    for(auto u:adj[necesar-1])
        a.push_back(u);
    sort(a.begin(),a.end());
    set<pair<long long,long long>>st;
    for(auto val:a)
    {
        while(!st.empty()&&(*st.begin()).first<=v[val].c)
        {
            long long nod=(*st.begin()).second;
            st.erase(st.begin());
            sum_aib(max(v[nod].b,1ll),dp2[nod]);
        }

        if(dp[val]==necesar)
        {
            dp2[val]=query_sum(v[val].a);
            if(dp2[val]>=mod)
                dp2[val]-=mod;
        }
        else if(dp[val]==necesar-1)
        {
            st.insert({v[val].d,val});
        }
    }

    while(!st.empty()&&(*st.begin()).first<=1e9)
    {
        long long nod=(*st.begin()).second;
        st.erase(st.begin());
        sum_aib(max(v[nod].b,1ll),dp2[nod]);
    }
    for(auto u:adj[necesar-1])
    {
        sum_aib(max(v[u].b,1ll),-dp2[u]);
        dp2[u]=0;
    }
}

int main()
{
    cin>>n;
    for(long long i=1; i<=n; i++)
    {
        cin>>v[i].a>>v[i].b>>v[i].c>>v[i].d;
        buffer.push_back(v[i].a);
        buffer.push_back(v[i].b);
        buffer.push_back(v[i].c);
        buffer.push_back(v[i].d);
    }

    norm();
    sort(v+1,v+n+1,[](trapezoid x,trapezoid y)
    {
        return x.c<y.c;
    });
    long long ans=0;
    set<pair<long long,long long>>sd;
    for(long long i=1; i<=n; i++)
    {
        while(!sd.empty()&&(*sd.begin()).first<=v[i].c)
        {
            long long nod=(*sd.begin()).second;
            update(v[nod].b,dp[nod]);
            sd.erase(sd.begin());
        }
        long long val=query(v[i].a);
        dp[i]=val+1;
        sd.insert({v[i].d,i});
        ans=max(ans,dp[i]);
    }
    adj[0].push_back(0);
    dp2[0]=1;
    clean_aib();
    for(long long i=1; i<=n; i++)
    {
        adj[dp[i]].push_back(i);
    }
    for(long long i=1; i<=ans; i++)
        calculate(i);

    long long modes=0;
    for(long long i=1; i<=n; i++)
    {
        modes+=dp2[i];
        if(modes>=mod)
            modes-=mod;
    }
    cout<<ans<<" ";
    cout<<modes<<'\n';
    return 0;
}

• Subtask 1: 12 / 100