#include <bits/stdc++.h>
using namespace std;
#define int long long
using ii = pair<int, int>;
const int N = 1e5 + 5;
int n, m;
ii dp[N];
vector<int> rrh;
vector<int> Lbound[N*4], Rbound[N*4];
struct info{
int a, b, c, d;
info(){}
info(int a, int b, int c, int d): a(a), b(b), c(c), d(d) {}
} x[N];
void init(){
for(int i = 1; i <= n; i++)
for(auto y : {x[i].a, x[i].b, x[i].c, x[i].d}) rrh.push_back(y);
sort(rrh.begin(), rrh.end());
rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end());
for(int i = 1; i <= n; i++){
x[i].a = lower_bound(rrh.begin(), rrh.end(), x[i].a) - rrh.begin() + 1;
x[i].b = lower_bound(rrh.begin(), rrh.end(), x[i].b) - rrh.begin() + 1;
x[i].c = lower_bound(rrh.begin(), rrh.end(), x[i].c) - rrh.begin() + 1;
x[i].d = lower_bound(rrh.begin(), rrh.end(), x[i].d) - rrh.begin() + 1;
Lbound[x[i].a].push_back(i);
Rbound[x[i].b].push_back(i);
}
m = rrh.size();
}
void add(int &x, int y){
x = (x + y) % 2023;
}
namespace it{
ii st[N<<4];
ii _merge(ii x, ii y){
ii res = {0, 0};
res.first = max(x.first, y.first);
if(res.first == x.first) add(res.second, x.second);
if(res.first == y.first) add(res.second, y.second);
return res;
}
void update(int pos, ii val, int tl = 0, int tr = m, int i = 1){
if(tl == tr){
if(val.first > st[i].first) st[i] = {val.first, 0};
if(st[i].first == val.first) add(st[i].second, val.second);
return;
}
int tm = tl + tr >> 1;
if(pos <= tm) update(pos, val, tl, tm, i<<1);
else update(pos, val, tm + 1, tr, i<<1|1);
st[i] = _merge(st[i<<1], st[i<<1|1]);
}
ii get(int l, int r, int tl = 0, int tr = m, int i = 1){
if(r < tl || tr < l || l > r) return {0, 0};
if(l <= tl && tr <= r) return st[i];
int tm = tl + tr >> 1;
return _merge(get(l, r, tl, tm, i<<1), get(l, r, tm + 1, tr, i<<1|1));
}
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
// #define task "test"
// if(fopen(task ".inp", "r")){
// freopen(task ".inp", "r", stdin);
// freopen(task ".out", "w", stdout);
// }
cin >> n;
for(int i = 1; i <= n; i++){
int a, b, c, d; cin >> a >> b >> c >> d;
x[i] = info(a, b, c, d);
}
init();
it::update(0, {0, 1});
int res = 0, cnt = 0;
for(int t = 1; t <= m; t++){
for(auto idx : Rbound[t]){
auto [a, b, c, d] = x[idx];
it::update(d, dp[idx]);
}
for(auto idx : Lbound[t]){
auto [a, b, c, d] = x[idx];
dp[idx] = it::get(0, c);
dp[idx].first += 1;
if(dp[idx].first > res) res = dp[idx].first, cnt = 0;
if(dp[idx].first == res) add(cnt, dp[idx].second);
}
}
cout << res << " " << cnt << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |