1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #include <cstdio>
#include <vector>
#include <algorithm>
#define fi first
#define se second
#define eb emplace_back
using namespace std;
template <class Type>
void read (Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
if (c == '-') flag = true;
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
if (flag) x = ~x + 1;
}
template <class Type, class ...Rest>
void read (Type &x, Rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
if (x < 0) putchar('-'), x = ~x + 1;
if (x > 9) write(x / 10);
putchar('0' + x % 10);
}
typedef long long L;
typedef pair <L, int> PLI;
const int N = 8e4 + 10, mod = 998244353;
void adj (int &x) { x += x >> 31 & mod; }
int n, m;
PLI f[N], tr[N];
PLI operator + (PLI x, int k) { return { x.fi + k, x.se }; }
struct Node { bool op; int a, b, c, d, v, id; } w[N];
bool cmp4 (Node &x, Node &y)
{ return x.d < y.d || (x.d == y.d && x.op > y.op); }
bool cmp3 (Node &x, Node &y)
{ return x.c < y.c || (x.c == y.c && cmp4(x, y)); }
bool cmp2 (Node &x, Node &y)
{ return x.b < y.b || (x.b == y.b && cmp3(x, y)); }
bool cmp1 (Node &x, Node &y)
{ return x.a < y.a || (x.a == y.a && cmp2(x, y)); }
void chkmax (PLI &x, PLI k)
{
if (k.fi > x.fi) x = k;
else if (k.fi == x.fi) adj(x.se += k.se - mod);
}
void add (int x, PLI k)
{
for (; x <= m; x += x & -x)
chkmax(tr[x], k);
}
PLI query (int x)
{
PLI res { 0, 0 };
for (; x; x -= x & -x)
chkmax(res, tr[x]);
return res;
}
void clear (int x)
{
for (; x <= m; x += x & -x)
tr[x] = { 0, 0 };
}
void cdq2 (int l, int r)
{
if (l == r) return;
int mid = l + r >> 1;
cdq2(l, mid);
vector <Node> tmp (w + l, w + r + 1);
sort(w + l, w + mid + 1, cmp3), sort(w + mid + 1, w + r + 1, cmp3);
for (int i = l, j = mid + 1; i <= mid || j <= r; )
{
for (; i <= mid && (j > r || !cmp3(w[j], w[i])); ++i)
if (w[i].op) add(w[i].d, f[w[i].id]);
for (; j <= r && (i > mid || cmp3(w[j], w[i])); ++j)
if (!w[j].op) chkmax(f[w[j].id], query(w[j].d) + w[j].v);
}
for (int i = l; i <= mid; ++i)
if (w[i].op) clear(w[i].d);
for (int i = l; i <= r; ++i) w[i] = tmp[i - l];
cdq2(mid + 1, r);
}
void cdq1 (int l, int r)
{
if (l == r) return;
int mid = l + r >> 1;
cdq1(l, mid);
vector <Node> tmp (w + l, w + r + 1);
for (int i = l; i <= mid; ++i) w[i].op = true;
sort(w + l, w + r + 1, cmp2);
cdq2(l, r);
for (int i = l; i <= r; ++i) w[i] = tmp[i - l];
cdq1(mid + 1, r);
}
int main ()
{
read(n, m);
vector <int> ws;
for (int i = 1; i <= n; ++i)
{
read(w[i].a, w[i].b, w[i].c, w[i].d, w[i].v);
ws.eb(w[i].d);
}
sort(ws.begin(), ws.end());
m = ws.erase(unique(ws.begin(), ws.end()), ws.end()) - ws.begin();
for (int i = 1; i <= n; ++i)
w[i].d = upper_bound(ws.begin(), ws.end(), w[i].d) - ws.begin();
sort(w + 1, w + n + 1, cmp1);
for (int i = 1; i <= n; ++i) f[w[i].id = i] = { w[i].v, 1 };
cdq1(1, n);
PLI res = { 0, 0 };
for (int i = 1; i <= n; ++i) chkmax(res, f[i]);
write(res.fi), puts(""), write(res.se);
return 0;
}
|