#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
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;
}
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 |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
604 KB |
Expected int32, but "10313130667392" found |
| 4 |
Incorrect |
2 ms |
680 KB |
Expected int32, but "-8550276992825950208" found |
| 5 |
Partially correct |
3 ms |
1368 KB |
Partially correct |
| 6 |
Incorrect |
5 ms |
2136 KB |
Expected int32, but "-8629080777422869056" found |
| 7 |
Incorrect |
5 ms |
1880 KB |
Expected int32, but "-3319866744691032064" found |
| 8 |
Partially correct |
7 ms |
2772 KB |
Partially correct |
| 9 |
Incorrect |
14 ms |
6240 KB |
Expected int32, but "2248786528710863832" found |
| 10 |
Incorrect |
24 ms |
9168 KB |
Expected int32, but "-5022802232222890496" found |
| 11 |
Incorrect |
35 ms |
14020 KB |
Expected int32, but "-1298419000938405298" found |
| 12 |
Incorrect |
79 ms |
27912 KB |
Expected int32, but "9183932486774365824" found |
| 13 |
Incorrect |
85 ms |
31364 KB |
Expected int32, but "-4195152448689438272" found |
| 14 |
Incorrect |
109 ms |
45960 KB |
Expected int32, but "-3175106568905838848" found |
| 15 |
Incorrect |
116 ms |
37080 KB |
Expected int32, but "-8026369531311511552" found |
| 16 |
Incorrect |
143 ms |
39360 KB |
Expected int32, but "6233362917342126368" found |
| 17 |
Incorrect |
144 ms |
50836 KB |
Expected int32, but "-7505826292837535760" found |
| 18 |
Incorrect |
114 ms |
38540 KB |
Expected int32, but "-6197299359079266322" found |
| 19 |
Incorrect |
144 ms |
52840 KB |
Expected int32, but "5619696618904563712" found |
| 20 |
Incorrect |
162 ms |
55612 KB |
Expected int32, but "-335818733633578353" found |
