//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define ill pair<ll,ll>
#define el cout<<'\n'
#define int long long
const ll mod=30013;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int nmax=5e5;
const int inf =2e9;
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
return uniform_int_distribution<int>(l, r) (rd);
}
int n;
struct polygon{
int a,b,c,d;
} polygons[nmax + 5];
int dp[nmax + 5];
int way[nmax + 5];
vector<ii>bucket[nmax + 5];
ii t[nmax * 4 + 5];
ii combine(ii x,ii y)
{
int val = max(x.fi,y.fi);
int cnt = 0;
if(val == x.fi)
cnt+=x.se;
if(val == y.fi)
cnt+=y.se;
cnt%=mod;cnt+=mod;cnt%=mod;
return (make_pair(val,cnt));
}
void update(int id,int l,int r,int pos,ii val)
{
if(l > pos || r < pos) return;
if(l == r)
{
if(t[id].fi < val.fi)
{
t[id].fi = val.fi;
t[id].se = val.se;
}
else
{
if(t[id].fi == val.fi)
t[id].se = (t[id].se + val.se)%mod;
}
return;
}
int mid = (l + r) >> 1;
update(id << 1,l,mid,pos,val);
update(id << 1 | 1,mid + 1,r,pos,val);
t[id] = combine(t[id << 1],t[id << 1 | 1]);
}
ii get(int id,int l,int r,int u,int v)
{
if(l > v || r < u)
{
return (make_pair(0,0));
}
if(u <= l && r <= v)
{
return t[id];
}
int mid = (l + r) >> 1;
return combine(get(id << 1,l,mid,u,v),get(id << 1 | 1,mid + 1,r,u,v));
}
vector<int>up;
vector<int>down;
void mapping()
{
for(int i=1;i<=n;i++)
{
up.push_back(polygons[i].a);
up.push_back(polygons[i].b);
}
sort(up.begin(),up.end());
up.erase(unique(up.begin(),up.end()),up.end());
for(int i=1;i<=n;i++)
{
polygons[i].a = lower_bound(up.begin(),up.end(),polygons[i].a) - up.begin() + 1;
polygons[i].b = lower_bound(up.begin(),up.end(),polygons[i].b) - up.begin() + 1;
}
for(int i=1;i<=n;i++)
{
down.push_back(polygons[i].c);
down.push_back(polygons[i].d);
}
sort(down.begin(),down.end());
down.erase(unique(down.begin(),down.end()),down.end());
for(int i=1;i<=n;i++)
{
polygons[i].c = lower_bound(down.begin(),down.end(),polygons[i].c) - down.begin() + 1;
polygons[i].d = lower_bound(down.begin(),down.end(),polygons[i].d) - down.begin() + 1;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> polygons[i].a >> polygons[i].b >> polygons[i].c >> polygons[i].d;
}
mapping();
for(int i=1;i<=n;i++)
{
bucket[polygons[i].a].push_back({1LL,i});
bucket[polygons[i].b].push_back({2LL,i});
}
int X = up.size();
int Y = down.size();
for(int i=1;i<=X;i++)
sort(bucket[i].begin(),bucket[i].end());
for(int i=1;i<=X;i++)
{
for(auto poly:bucket[i])
{
int type = poly.fi;
int id = poly.se;
if(type == 1)
{
ii tmp = get(1,1,Y,1,polygons[id].c - 1);
dp[id] = tmp.fi + 1;
way[id] = tmp.se;
if(dp[id] == 1)
way[id] = 1;
}
else
{
update(1,1,Y,polygons[id].d,make_pair(dp[id],way[id]));
}
}
}
ii ans = {0,0};
for(int i=1;i<=n;i++)
ans = combine(ans,make_pair(dp[i],way[i]));
cout << ans.fi << " " << ans.se;
}
// "Can i get a kiss? And can u make it last forever?"
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
