#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define N 100005
#define MOD 30013
using namespace std;
int n, a[N], b[N], c[N], d[N], rr[4*N];
int dp[N], dem[N];
void inline ADD(int &a, int b) {a += b; if (a >= MOD) a -= MOD;}
struct event
{
int u, v, type, id;
event(int _u=0, int _v=0, int _type=0, int _id=0) : u(_u), v(_v), type(_type), id(_id) {}
bool operator < (const event &rhs) const {
return u < rhs.u;
}
}e[N*2];
struct IntervalTree
{
int t[N << 4], cnt[N << 4];
void update(int l, int r, int id, int x, int val, int cntWay)
{
if (l > x || r < x) return;
if (l == r)
{
if (val < t[id]) return;
else if (t[id] == val) ADD(cnt[id], cntWay);
else cnt[id] = cntWay;
t[id] = val;
return;
}
int mid = (r + l)/2;
if (x <= mid) update(l, mid, id*2, x, val, cntWay);
else update(mid+1, r, id*2+1, x, val, cntWay);
t[id] = max(t[id*2], t[id*2+1]);
cnt[id] = 0;
if (t[id] == t[id*2]) ADD(cnt[id], cnt[id*2]);
if (t[id] == t[id*2+1]) ADD(cnt[id], cnt[id*2+1]);
}
int get(int l, int r, int id, int x, int y)
{
if (l > y || r < x) return 0;
if (l >= x && r <= y) return t[id];
int mid = (r + l)/2;
int a = get(l, mid, id*2, x, y);
int b = get(mid+1, r, id*2+1, x, y);
return max(a, b);
}
int getWay(int l, int r, int id, int x, int y, int val)
{
if (l > y || r < x) return 0;
if (l >= x && r <= y) return (val == t[id])*cnt[id];
int mid = (r + l)/2;
int a = getWay(l, mid, id*2, x, y, val);
int b = getWay(mid+1, r, id*2+1, x, y, val);
ADD(a, b);
return a;
}
}t;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("TRAPEZOID.INP", "r", stdin);
cin >> n;
int cur = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i] >> b[i] >> c[i] >> d[i];
rr[++cur] = a[i]; rr[++cur] = b[i];
rr[++cur] = c[i]; rr[++cur] = d[i];
}
sort(rr+1, rr+cur+1);
cur = unique(rr+1, rr+cur+1) - rr - 1;
for (int i = 1; i <= n; i++)
{
a[i] = lower_bound(rr+1, rr+cur+1, a[i]) - rr;
b[i] = lower_bound(rr+1, rr+cur+1, b[i]) - rr;
c[i] = lower_bound(rr+1, rr+cur+1, c[i]) - rr;
d[i] = lower_bound(rr+1, rr+cur+1, d[i]) - rr;
}
cur = 0;
for (int i = 1; i <= n; i++)
{
e[++cur] = event(a[i], c[i], 0, i);
e[++cur] = event(b[i], d[i], 1, i);
}
sort(e+1, e+cur+1);
for (int i = 1; i <= cur; i++)
{
if (e[i].type == 0)
{
dp[e[i].id] = t.get(1, 4*n, 1, 1, e[i].v-1) + 1;
dem[e[i].id] = max(1, t.getWay(1, 4*n, 1, 1, e[i].v-1, dp[e[i].id] - 1));
}
else t.update(1, 4*n, 1, e[i].v, dp[e[i].id], dem[e[i].id]);
}
int res = *max_element(dp+1, dp+n+1);
int ans = 0;
for (int i = 1; i <= n; i++)
if (dp[i] == res)
ADD(ans, dem[i]);
cout <<res<<" "<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
3576 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3576 KB |
Output is correct |
| 3 |
Correct |
5 ms |
3748 KB |
Output is correct |
| 4 |
Correct |
6 ms |
3748 KB |
Output is correct |
| 5 |
Correct |
8 ms |
3884 KB |
Output is correct |
| 6 |
Correct |
9 ms |
4200 KB |
Output is correct |
| 7 |
Correct |
11 ms |
4272 KB |
Output is correct |
| 8 |
Correct |
14 ms |
4752 KB |
Output is correct |
| 9 |
Correct |
24 ms |
5324 KB |
Output is correct |
| 10 |
Correct |
42 ms |
6964 KB |
Output is correct |
| 11 |
Correct |
59 ms |
8308 KB |
Output is correct |
| 12 |
Correct |
119 ms |
11828 KB |
Output is correct |
| 13 |
Correct |
150 ms |
14676 KB |
Output is correct |
| 14 |
Correct |
163 ms |
20824 KB |
Output is correct |
| 15 |
Correct |
185 ms |
20980 KB |
Output is correct |
| 16 |
Correct |
188 ms |
24160 KB |
Output is correct |
| 17 |
Correct |
224 ms |
27648 KB |
Output is correct |
| 18 |
Correct |
164 ms |
27648 KB |
Output is correct |
| 19 |
Correct |
216 ms |
31816 KB |
Output is correct |
| 20 |
Correct |
236 ms |
34628 KB |
Output is correct |
