#include<bits/stdc++.h>
using namespace std;
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << "[";
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << "]";
}
//var
LL T;
const int INF = 1e9;
const LL MOD = 30013;
struct mint {
int x;
mint() : x(0) {}
template <class T> mint(T value) : x(value % MOD) { if (x < 0) x += MOD; }
mint & operator+=(const mint &oth) { x += oth.x; if (x >= MOD) x -= MOD; return *this; }
mint & operator-=(const mint &oth) { x -= oth.x; if (x < 0) x += MOD; return *this; }
mint & operator*=(const mint &oth) { x = (long long) x * oth.x % MOD; return *this; }
friend mint operator+(mint l, const mint &r) { return l += r; }
friend mint operator-(mint l, const mint &r) { return l -= r; }
friend mint operator*(mint l, const mint &r) { return l *= r; }
mint & operator--() { if (--x == -1) x = MOD - 1; return *this; }
mint & operator++() { if (++x == MOD) x = 0; return *this; }
mint operator--(int) { mint temp = *this; --*this; return temp; }
mint operator++(int) { mint temp = *this; ++*this; return temp; }
mint operator-() const { return 0 - *this; }
mint operator+() const { return *this; }
friend bool operator==(const mint &l, const mint &r) { return l.x == r.x; }
friend bool operator!=(const mint &l, const mint &r) { return l.x != r.x; }
friend ostream & operator<<(ostream &out, const mint &a) { return out << a.x; }
mint pow(long long e = MOD - 2) const {
mint ans = 1, b = *this;
while (e > 0) {
if (e % 2 == 1) {
ans *= b;
}
b *= b;
e /= 2;
}
return ans;
}
};
struct Info {
int dp;
mint ways;
Info(int dp, mint ways) : dp(dp), ways(ways) {}
Info(int dp) : dp(dp), ways(0) {}
};
Info max(const Info& a, const Info& b) {
if (a.dp > b.dp) { return a; }
if (b.dp > a.dp) { return b; }
return Info(a.dp, a.ways + b.ways);
};
template <typename T, int SZ>
struct PST {
struct Node {
T val;
int c[2];
Node() : val(INF, 0) {
c[0] = c[1] = 0;
}
};
static const int LIM = 3.1e6;
Node d[LIM];
int nxt = 0;
int copy(int t) { d[nxt] = d[t]; nxt++; assert(nxt <= LIM); return nxt - 1;}
T comb(const T& a, const T& b) { return max(a, b); }
void pull(int c) { d[c].val = comb(d[d[c].c[0]].val, d[d[c].c[1]].val); }
T query(int lo, int hi, int t, int l, int r) {
if (lo >= r || hi <= l) return T(-INF, 0);
if (lo <= l && r <= hi) return d[t].val;
int m = (l + r) / 2;
T lef = query(lo, hi, d[t].c[0], l, m);
T rig = query(lo, hi, d[t].c[1], m, r);
return comb(lef, rig);
}
int upd(int i, const T& v, int t, int l, int r) {
int x = copy(t);
if (r - l == 1) {
d[x].val = max(d[x].val, v);
return x;
}
int m = (l + r) / 2;
if (i < m) {
d[x].c[0] = upd(i, v, d[x].c[0], l, m);
}else{
d[x].c[1] = upd(i, v, d[x].c[1], m, r);
}
pull(x);
return x;
}
int build(const vector<T>& a, int l, int r) {
int c = nxt++;
if (r - l == 1) {
if (l < (int)a.size()) d[c].val = a[l];
return c;
}
int m = (l + r) / 2;
d[c].c[0] = build(a, l, m);
d[c].c[1] = build(a, m, r);
pull(c);
return c;
}
vector<int> rts;
void update_time(int i, const T& v) {
//debug(rts);
rts.pb(upd(i, v, rts.back(), 0, SZ));
}
void build(const vector<T>& a) {
rts.pb(build(a, 0, SZ));
}
T query_time(int ti, int lo, int hi) {
return query(lo, hi, rts[ti], 0, SZ);
}
};
PST<Info, 1 << 18> pst;
void solve() {
int n;
cin >> n;
vector<array<int, 4>> a(n);
for (auto& [x, y, z, d] : a)
cin >> x >> y >> z >> d;
vector<LL> a_ricky, b_ricky;
for (auto [x, y, z, d] : a) {
a_ricky.pb(x);
a_ricky.pb(y);
b_ricky.pb(z);
b_ricky.pb(d);
}
sort(all(a_ricky));
sort(all(b_ricky));
a_ricky.erase(unique(all(a_ricky)), a_ricky.end());
b_ricky.erase(unique(all(b_ricky)), b_ricky.end());
auto get_a = [&](const int& g) -> LL {
return lower_bound(all(a_ricky), g) - a_ricky.begin() + 1;
};
auto get_b = [&](const int& g) -> LL {
return lower_bound(all(b_ricky), g) - b_ricky.begin() + 1;
};
int A = (int)a_ricky.size();
int B = (int)b_ricky.size();
vector sweep(A + 1, vector<array<LL, 3>>());
for (auto& [x, y, z, d] : a) {
sweep[get_a(y)].pb({get_a(x), get_b(z), get_b(d)});
}
//debug(sweep);
vector<Info> init(B + 1, Info(-INF, 0)); init[0] = Info(0, 1);
pst.build(init);
//vector<node<Info>*> roots = {(tree.build(init))};
Info ans(-INF, 0);
vector<int> time_of = {0};
FOR (i, A) {
for (auto& [l, x, y] : sweep[i]) {
Info trans = pst.query_time(time_of[l - 1], 0, x);
Info next = Info(trans.dp + 1, trans.ways);
ans = max(ans, next);
Info cur = pst.query_time(pst.rts.size() - 1, y, y + 1);
if (next.dp >= cur.dp)
pst.update_time(y, next);
}
time_of.pb((int)pst.rts.size() - 1);
}
cout << ans.dp << " " << ans.ways << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
T = 1;
//cin >> T;
FOR(t, T)
solve();
cout.flush();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
48804 KB |
Output is correct |
| 2 |
Correct |
25 ms |
48952 KB |
Output is correct |
| 3 |
Correct |
26 ms |
48908 KB |
Output is correct |
| 4 |
Correct |
27 ms |
48980 KB |
Output is correct |
| 5 |
Correct |
27 ms |
49100 KB |
Output is correct |
| 6 |
Correct |
28 ms |
49320 KB |
Output is correct |
| 7 |
Correct |
30 ms |
49384 KB |
Output is correct |
| 8 |
Correct |
34 ms |
49748 KB |
Output is correct |
| 9 |
Correct |
40 ms |
50436 KB |
Output is correct |
| 10 |
Correct |
51 ms |
52032 KB |
Output is correct |
| 11 |
Correct |
61 ms |
52800 KB |
Output is correct |
| 12 |
Correct |
101 ms |
56772 KB |
Output is correct |
| 13 |
Correct |
151 ms |
58216 KB |
Output is correct |
| 14 |
Correct |
142 ms |
60216 KB |
Output is correct |
| 15 |
Correct |
158 ms |
60972 KB |
Output is correct |
| 16 |
Correct |
171 ms |
61796 KB |
Output is correct |
| 17 |
Correct |
169 ms |
62540 KB |
Output is correct |
| 18 |
Correct |
157 ms |
63280 KB |
Output is correct |
| 19 |
Correct |
174 ms |
63944 KB |
Output is correct |
| 20 |
Correct |
192 ms |
64688 KB |
Output is correct |
