제출 #1129652

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

trapezoid

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

int main()
{
    cin>>n;
    for(int 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;
    });
    int ans=0;
    set<pair<int,int>>sd;
    for(int i=1; i<=n; i++)
    {
        while(!sd.empty()&&(*sd.begin()).first<=v[i].c)
        {
            int nod=(*sd.begin()).second;
            update(v[nod].b,dp[nod]);
            sd.erase(sd.begin());
        }
        int 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(int i=1; i<=n; i++)
    {
        adj[dp[i]].push_back(i);
    }
    for(int i=1; i<=ans; i++)
        calculate(i);

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

• Subtask 1: 43 / 100