#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] ;
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) ;
int ans = 0 ;
for(int i = 0 ; i < n ; ++i)
{
LIS[i] = tree.query(v[i][2]-1) + 1 ;
ans = max(ans , LIS[i]) ;
tree.update(v[i][3] , LIS[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 ;
for(int i = 0 ; i < n ; ++i)
{
int x = treecnt[LIS[i]-1].query(v[i][2]-1) ;
if(LIS[i] == ans)
cnt = (cnt + x) % mod ;
treecnt[LIS[i]].update(v[i][3] , x) ;
}
return cout<<ans<<" "<<cnt<<"\n" , 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2688 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
2816 KB |
Output isn't correct |
| 4 |
Correct |
7 ms |
2816 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
3072 KB |
Output isn't correct |
| 6 |
Incorrect |
11 ms |
3200 KB |
Output isn't correct |
| 7 |
Correct |
11 ms |
3456 KB |
Output is correct |
| 8 |
Incorrect |
13 ms |
3584 KB |
Output isn't correct |
| 9 |
Incorrect |
21 ms |
4544 KB |
Output isn't correct |
| 10 |
Correct |
34 ms |
6332 KB |
Output is correct |
| 11 |
Incorrect |
43 ms |
7220 KB |
Output isn't correct |
| 12 |
Incorrect |
87 ms |
11820 KB |
Output isn't correct |
| 13 |
Incorrect |
109 ms |
13612 KB |
Output isn't correct |
| 14 |
Incorrect |
131 ms |
15528 KB |
Output isn't correct |
| 15 |
Incorrect |
137 ms |
16300 KB |
Output isn't correct |
| 16 |
Incorrect |
150 ms |
17372 KB |
Output isn't correct |
| 17 |
Incorrect |
156 ms |
18236 KB |
Output isn't correct |
| 18 |
Correct |
148 ms |
19112 KB |
Output is correct |
| 19 |
Incorrect |
159 ms |
19920 KB |
Output isn't correct |
| 20 |
Incorrect |
188 ms |
21224 KB |
Output isn't correct |
