| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1129657 | I_FloPPed21 | 사다리꼴 (balkan11_trapezoid) | C++20 | 0 ms | 0 KiB |
#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;
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];
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);
}
else if(dp[val]==necesar-1)
{
st.insert({v[val].d,val});
}
}
while(!st.empty())
{
int nod=(*st.begin()).second;
st.erase(st.begin());
sum_aib(max(v[nod].b,1),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(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];
modes%=mod;
}
cout<<ans<<" ";
cout<<modes<<'\n';
return 0;
}