#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mid ((x + y) / 2)
#define left (ind * 2)
#define right (ind * 2 + 1)
#define timer ((double)clock() / CLOCKS_PER_SEC)
#define endl "\n"
#define spc " "
#define d1(x) cerr<<#x<<":"<<x<<endl
#define d2(x, y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define d3(x, y, z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long int lli;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<double, double> dd;
const int N = (int)(1e6 + 5);
const int LOG = (int)(20);
const int mod = (int)(30013);
int n, ans, tot;
ii tree[N << 2], dp[N];
set<int> s;
unordered_map<int, int> mp;
vector<ii> ev;
struct trap {
int a, b, c, d;
void read() {
cin >> a >> b >> c >> d;
}
void compress() {
a = mp[a];
b = mp[b];
c = mp[c];
d = mp[d];
}
}ar[N];
ii merge(ii x, ii y) {
ii re;
if(x.fi == y.fi)
return {x.fi, (x.se + y.se) % mod};
else
return max(x, y);
}
void upd(int ind, int x, int y, int a, ii val) {
if(a < x || y < a)
return;
if(x == y) {
tree[ind] = val;
return;
}
upd(left, x, mid, a, val);
upd(right, mid + 1, y, a, val);
tree[ind] = merge(tree[left], tree[right]);
}
ii get(int ind, int x, int y, int a, int b) {
if(y < a || b < x)
return {-1, 0};
if(a <= x && y <= b)
return tree[ind];
return merge(get(left, x, mid, a, b), get(right, mid + 1, y, a, b));
}
int main() {
fast_io();
//freopen("inp.in", "r", stdin);
cin >> n;
for(int i = 1; i <= n; i++) {
ar[i].read();
s.insert(ar[i].a);
s.insert(ar[i].b);
s.insert(ar[i].c);
s.insert(ar[i].d);
}
int t = 0;
for(auto i : s)
mp[i] = ++t;
for(int i = 1; i <= n; i++)
ar[i].compress();
for(int i = 1; i <= n; i++) {
ev.pb({i, 0});
ev.pb({i, 1});
}
sort(ev.begin(), ev.end(), [&] (ii x, ii y) {
int cmpx, cmpy;
if(x.se == 0)
cmpx = ar[x.fi].c;
else
cmpx = ar[x.fi].d;
if(y.se == 0)
cmpy = ar[y.fi].c;
else
cmpy = ar[y.fi].d;
return cmpx < cmpy;
});
upd(1, 0, t, 0, {0, 1});
for(auto i : ev) {
int ind = i.fi;
if(i.se == 0) {
ii g = get(1, 0, t, 0, ar[ind].a - 1);
dp[ind] = {g.fi + 1, g.se};
}
else
upd(1, 0, t, ar[ind].b, dp[ind]);
ans = max(ans, dp[ind].fi);
}
for(int i = 1; i <= n; i++)
if(dp[i].fi == ans) {
tot += dp[i].se;
tot %= mod;
}
cout << ans << spc << tot;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
512 KB |
Output is correct |
| 4 |
Correct |
4 ms |
640 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1408 KB |
Output is correct |
| 6 |
Correct |
10 ms |
1792 KB |
Output is correct |
| 7 |
Correct |
11 ms |
1536 KB |
Output is correct |
| 8 |
Correct |
21 ms |
2432 KB |
Output is correct |
| 9 |
Correct |
53 ms |
5508 KB |
Output is correct |
| 10 |
Correct |
54 ms |
6436 KB |
Output is correct |
| 11 |
Correct |
131 ms |
12392 KB |
Output is correct |
| 12 |
Correct |
253 ms |
25272 KB |
Output is correct |
| 13 |
Correct |
304 ms |
27012 KB |
Output is correct |
| 14 |
Correct |
424 ms |
37892 KB |
Output is correct |
| 15 |
Correct |
397 ms |
33284 KB |
Output is correct |
| 16 |
Correct |
472 ms |
34692 KB |
Output is correct |
| 17 |
Execution timed out |
533 ms |
43456 KB |
Time limit exceeded |
| 18 |
Correct |
319 ms |
27164 KB |
Output is correct |
| 19 |
Correct |
472 ms |
43464 KB |
Output is correct |
| 20 |
Execution timed out |
537 ms |
46328 KB |
Time limit exceeded |
