제출 #1129646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129646		I_FloPPed21	사다리꼴 (balkan11_trapezoid)	C++20	40 / 100	361 ms	20736 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;
}
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]);
    }
    cout<<ans<<'\n';
    cout<<0<<'\n';
    return 0;
}

• Subtask 1: 40 / 100