/* code by PixelCat */
/* meow owo */
#include <bits/stdc++.h>
#define int LL //__int128
#define double long double
using namespace std;
using LL = long long;
// using i128 = __int128_t;
using ull = unsigned long long;
using pii = pair<int, int>;
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair
#define MOD 30013
// #define MOD (int)(998244353)
// #define MOD (int)((LL)1'000'000'007)
#define INF (int)(4e18)
#define EPS (1e-6)
#ifdef NYAOWO
#include "/home/pixelcat/yodayo/code/meow/library/debug.hpp"
inline void USACO(const string &s) {
cerr << "USACO: " << s << "\n";
}
#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
#endif
inline void NYA() {
ios::sync_with_stdio(false);
cin.tie(0);
}
inline int gcd(int a, int b) {
return __gcd(a, b);
}
inline int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod = MOD) {
int ans = 1;
for (; p; p >>= 1, b = b * b % mod)
if (p & 1) ans = ans * b % mod;
return ans;
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
if (_b > _a) _a = _b;
}
// mt19937_64 rng(
// chrono::steady_clock::now().time_since_epoch().count());
void inline cmax(pii &pa, const pii &pb) {
// max, count
if(pa.F < pb.F) {
pa = pb;
} else if(pa.F == pb.F) {
pa.S += pb.S;
if(pa.S >= MOD) pa.S -= MOD;
}
}
const int MAXN = 200020;
#define LO(x) ((x) & (-x))
struct BIT {
int n;
pii a[MAXN];
void init(int _n) {
n = _n;
fill(a, a + MAXN, pii(0, 0));
}
void upd(int i, const pii &p) {
while(i <= n) {
cmax(a[i], p);
i += LO(i);
}
}
pii qry(int i) {
pii ans(0, 0);
while(i) {
cmax(ans, a[i]);
i -= LO(i);
}
return ans;
}
} bit;
int32_t main() {
NYA();
// nyaacho >/////<
// miku sama bless me >/////<
int n; cin >> n;
bit.init(200000);
struct EV {
int id, x, y, io;
}; vector<EV> v;
vector<pii> tmp(n + 5);
{ // input
vector<int> aly;
For(i, 1, n) {
int a, b, c, d; cin >> a >> b >> c >> d;
v.push_back({i, a, c, 0});
v.push_back({i, b, d, 1});
aly.eb(c); aly.eb(d);
}
sort(all(aly)); aly.erase(unique(all(aly)), aly.end());
for(auto &e:v) {
e.y = lower_bound(all(aly), e.y) - aly.begin() + 1;
}
}
sort(all(v), [&](const EV &a, const EV &b) {
return a.x < b.x;
});
for(auto &e:v) {
// debug(e.id, e.y, e.io);
if(e.io == 0) {
tmp[e.id] = bit.qry(e.y);
tmp[e.id].S += (tmp[e.id].F == 0);
tmp[e.id].F++;
} else {
bit.upd(e.y, tmp[e.id]);
}
}
auto res = bit.qry(200000);
cout << res.F << " " << res.S << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3412 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3460 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3540 KB |
Output is correct |
| 5 |
Correct |
4 ms |
3668 KB |
Output is correct |
| 6 |
Correct |
4 ms |
3892 KB |
Output is correct |
| 7 |
Correct |
5 ms |
3924 KB |
Output is correct |
| 8 |
Correct |
7 ms |
4176 KB |
Output is correct |
| 9 |
Correct |
10 ms |
5068 KB |
Output is correct |
| 10 |
Correct |
20 ms |
6836 KB |
Output is correct |
| 11 |
Correct |
22 ms |
6984 KB |
Output is correct |
| 12 |
Correct |
45 ms |
10500 KB |
Output is correct |
| 13 |
Correct |
53 ms |
11648 KB |
Output is correct |
| 14 |
Correct |
64 ms |
16764 KB |
Output is correct |
| 15 |
Correct |
71 ms |
16688 KB |
Output is correct |
| 16 |
Correct |
84 ms |
16764 KB |
Output is correct |
| 17 |
Correct |
82 ms |
17068 KB |
Output is correct |
| 18 |
Correct |
78 ms |
16988 KB |
Output is correct |
| 19 |
Correct |
85 ms |
17020 KB |
Output is correct |
| 20 |
Correct |
90 ms |
17508 KB |
Output is correct |
