#include <bits/stdc++.h>
using namespace std ;
const int mod = 30013 ;
const int MAX = 1e5 + 10 ;
struct segment_tree
{
vector<int>v ;
vector<long long> tree ;
int sz ;
bool flag ;
void init(vector<int>v2 , bool t)
{
if(t == 0)
flag = 0 ;
else
flag = 1 ;
sz = (int)v2.size() ;
v = v2 ;
sort(v.begin() , v.end()) ;
tree.resize(sz*4+10) ;
for(int i = 0 ; i <= sz*4 ; ++i)
tree[i] = 0 ;
}
int getidx1(long long idx)
{
int idx2 = lower_bound(v.begin() , v.end() , idx) - v.begin() ;
return idx2 ;
}
int getidx2(long long idx)
{
int idx2 = upper_bound(v.begin() , v.end() , idx) - v.begin() ;
idx2-- ;
return idx2 ;
}
void update(int node , int l , int r , int idx , long long v)
{
if(idx > r || idx < l || idx < 0)
return ;
if(l == r)
{
if(flag == 0)
tree[node] = max(tree[node] , v) ;
else
tree[node] = (tree[node] + v) % mod ;
return ;
}
int mid = (l + r) >> 1 ;
update(node << 1 , l , mid , idx , v) ;
update(node << 1 | 1 , mid+1 , r , idx , v) ;
if(flag == 0)
tree[node] = max(tree[node << 1] , tree[node << 1 | 1]) ;
else
tree[node] = (tree[node << 1] + tree[node << 1 | 1]) % mod ;
}
long long query(int node , int l , int r , int from , int to)
{
if(from > r || to < l || from > to)
return 0 ;
if(l >= from && r <= to)
return tree[node] ;
int mid = (l + r) >> 1 ;
long long a = query(node << 1 , l , mid , from , to) ;
long long b = query(node << 1 | 1 , mid+1 , r , from , to) ;
if(flag == 0)
return max(a , b) ;
else
return (a + b) % mod ;
}
void update(long long idx , long long val)
{
idx = getidx1(idx) ;
update(1 , 0 , sz , idx , val) ;
}
long long query(long long idx)
{
idx = getidx2(idx) ;
return query(1 , 0 , sz , 0 , idx) ;
}
};
int arr[MAX] ;
int n ;
vector< array<int , 4> >v ;
vector<int>v2 ;
vector<int>lis[MAX] ;
int LIS[MAX] , ways[MAX] ;
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n ;
for(int i = 0 ; i < n ; ++i)
{
int l1 , r1 , l2 , r2 ;
cin>>l1>>r1>>l2>>r2 ;
v.push_back({l1 , r1 , l2 , r2}) ;
v2.push_back(r2) ;
}
sort(v.begin() , v.end()) ;
segment_tree tree ;
tree.init(v2 , 0) ;
set< pair<int , int> >s ;
int ans = 0 ;
for(int i = 0 ; i < n ; ++i)
{
while(s.size() > 0)
{
pair<int , int>p = *s.begin() ;
if(p.first >= v[i][0])
break ;
tree.update(v[p.second][3] , LIS[p.second]) ;
s.erase(p) ;
}
LIS[i] = tree.query(v[i][2]-1) + 1 ;
ans = max(ans , LIS[i]) ;
s.insert({v[i][1] , i}) ;
lis[LIS[i]].push_back(v[i][3]) ;
}
vector<segment_tree>treecnt(n+1) ;
treecnt[0].init({-1} , 1) ;
treecnt[0].update(-1 , 1) ;
for(int i = 1 ; i <= n ; ++i)
{
if(lis[i].size())
treecnt[i].init(lis[i] , 1) ;
}
int cnt = 0 ;
s.clear() ;
for(int i = 0 ; i < n ; ++i)
{
while(s.size() > 0)
{
pair<int , int>p = *s.begin() ;
if(p.first >= v[i][0])
break ;
treecnt[LIS[p.second]].update(v[p.second][3] , ways[p.second]) ;
s.erase(p) ;
}
ways[i] = treecnt[LIS[i]-1].query(v[i][2]-1) ;
if(LIS[i] == ans)
cnt = (cnt + ways[i]) % mod ;
s.insert({v[i][1] , i}) ;
}
return cout<<ans<<" "<<cnt<<"\n" , 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2816 KB |
Output is correct |
| 4 |
Correct |
7 ms |
2944 KB |
Output is correct |
| 5 |
Correct |
9 ms |
3072 KB |
Output is correct |
| 6 |
Correct |
12 ms |
3200 KB |
Output is correct |
| 7 |
Correct |
12 ms |
3328 KB |
Output is correct |
| 8 |
Correct |
15 ms |
3584 KB |
Output is correct |
| 9 |
Correct |
25 ms |
4416 KB |
Output is correct |
| 10 |
Correct |
42 ms |
6068 KB |
Output is correct |
| 11 |
Correct |
56 ms |
6708 KB |
Output is correct |
| 12 |
Correct |
114 ms |
10800 KB |
Output is correct |
| 13 |
Correct |
140 ms |
12476 KB |
Output is correct |
| 14 |
Correct |
163 ms |
13992 KB |
Output is correct |
| 15 |
Correct |
193 ms |
14888 KB |
Output is correct |
| 16 |
Correct |
210 ms |
15928 KB |
Output is correct |
| 17 |
Correct |
206 ms |
16552 KB |
Output is correct |
| 18 |
Correct |
183 ms |
17200 KB |
Output is correct |
| 19 |
Correct |
213 ms |
17968 KB |
Output is correct |
| 20 |
Correct |
255 ms |
18856 KB |
Output is correct |
