#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9, mod = 30013;
struct point{
ll x, y, t, id;
};
struct Node{
ll lis = 0, cnt = 0;
};
Node merge(Node a, Node b){
Node res;
res.lis = max(a.lis, b.lis);
if(a.lis > b.lis){
res.cnt = a.cnt;
}else if(a.lis < b.lis){
res.cnt = b.cnt;
}else{
res.cnt = a.cnt+b.cnt;
}
res.cnt %= mod;
return res;
}
struct SegmentTree{
int n, N;
vector<Node> T;
SegmentTree(int n) : n(n){
N = 1;
while(N < n) N*=2;
T.resize(N*2+1, Node());
};
void modify(int i, Node x){
auto modify = [&](auto self, int node, int low, int high, int i, Node x) -> void{
if(low == high){
T[node] = x;
return;
}
int mid = (low+high)/2;
if(i <= mid){
self(self, node*2, low, mid, i, x);
}else{
self(self, node*2+1, mid+1, high, i, x);
}
T[node] = merge(T[node*2], T[node*2+1]);
};
modify(modify, 1, 1, N, i, x);
}
Node rangeQuery(int l, int r){
auto rangeQuery = [&](auto self, int node, int low, int high, int l, int r) -> Node{
if(low > r || l > high) return Node();
if(low >= l && r >= high) return T[node];
int mid = (low+high)/2;
return merge(self(self, node*2, low, mid, l, r), self(self, node*2+1, mid+1, high, l, r));
};
return rangeQuery(rangeQuery, 1, 1, N, l, r);
}
};
struct normalize{
vector<ll> poi, pot;
void add(ll x){
poi.push_back(x);
}
void start(){
sort(poi.begin(), poi.end());
pot.clear();
pot.push_back(poi[0]);
for(int i = 1; i < (int)poi.size(); i++){
if(poi[i] != poi[i-1]){
pot.push_back(poi[i]);
}
}
}
int encode(ll x){
return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1;
}
};
void solve(){
int n;
cin >> n;
vector<vector<point>> a(n+1, vector<point>(2));
for(int i = 1; i <= n; i++){
cin >> a[i][0].x >> a[i][1].x >> a[i][0].y >> a[i][1].y;
a[i][0].t = 0;
a[i][1].t = 1;
a[i][0].id = a[i][1].id = i;
}
normalize norm;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= 1; j++){
norm.add(a[i][j].x);
norm.add(a[i][j].y);
}
}
norm.start();
for(int i = 1; i <= n; i++){
for(int j = 0; j <= 1; j++){
a[i][j].x = norm.encode(a[i][j].x);
a[i][j].y = norm.encode(a[i][j].y);
}
}
int N = norm.pot.size();
vector<vector<point>> b(N+1);
for(int i = 1; i <= n; i++){
b[a[i][0].x].push_back(a[i][0]);
b[a[i][1].x].push_back(a[i][1]);
}
SegmentTree T(N+1);
vector<Node> f(n+1);
for(int i = 1; i <= N; i++){
sort(b[i].begin(), b[i].end(), [&](point a, point b){return a.t < b.t;});
for(auto it : b[i]){
if(it.t == 0){
Node prv = T.rangeQuery(1, it.y);
f[it.id] = merge({prv.lis+1, prv.cnt}, {1, 1});
}else{
T.modify(it.y, f[it.id]);
}
}
}
Node ans = {0, 0};
for(int i = 1; i <= n; i++){
ans = merge(ans, f[i]);
}
cout << ans.lis << " " << ans.cnt << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1372 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1880 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1884 KB |
Output is correct |
| 8 |
Correct |
6 ms |
2520 KB |
Output is correct |
| 9 |
Correct |
15 ms |
5984 KB |
Output is correct |
| 10 |
Correct |
23 ms |
8576 KB |
Output is correct |
| 11 |
Correct |
33 ms |
13272 KB |
Output is correct |
| 12 |
Correct |
73 ms |
26692 KB |
Output is correct |
| 13 |
Correct |
94 ms |
29844 KB |
Output is correct |
| 14 |
Correct |
110 ms |
45020 KB |
Output is correct |
| 15 |
Correct |
116 ms |
34036 KB |
Output is correct |
| 16 |
Correct |
137 ms |
36352 KB |
Output is correct |
| 17 |
Correct |
129 ms |
46868 KB |
Output is correct |
| 18 |
Correct |
114 ms |
37388 KB |
Output is correct |
| 19 |
Correct |
148 ms |
49952 KB |
Output is correct |
| 20 |
Correct |
156 ms |
51520 KB |
Output is correct |
