#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int N = 30013;
struct Node {
int best, count;
Node operator + (const Node &other) {
if (best == other.best)
return {best, (other.count + count) % MOD};
else if (best > other.best)
return *this;
else
return other;
}
} aint[4 * N], ans;
void update (int nod, int st, int dr, int poz, Node val) {
if (st == dr) {
aint[nod] = val;
return;
}
int mij = (st + dr) / 2;
if (poz <= mij)
update(2 * nod, st, mij, poz, val);
else
update(2 * nod + 1, mij + 1, dr, poz, val);
aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
void query (int nod, int st, int dr, int a, int b) {
if (a <= st && dr <= b) {
ans = ans + aint[nod];
return;
}
int mij = (st + dr) / 2;
if (a <= mij)
query(2 * nod, st, mij, a, b);
if (b > mij)
query(2 * nod + 1, mij + 1, dr, a, b);
}
struct event {
int type, time, x, ind;
bool operator < (const event other) {
return time < other.time;
}
} v[N];
int a[N][4];
int n;
Node dp[N];
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
vector<int>idk;
for (int i = 1; i <= n; i++) {
for (auto j : {0, 1, 2, 3})
cin >> a[i][j];
idk.push_back(a[i][2]);
idk.push_back(a[i][3]);
}
sort(idk.begin(), idk.end());
for (int i = 1; i <= n; i++) {
v[2 * i - 1] = {0, a[i][0], (int)(lower_bound(idk.begin(), idk.end(), a[i][2]) - idk.begin() + 1), i};
v[2 * i] = {1, a[i][1], (int)(lower_bound(idk.begin(), idk.end(), a[i][3]) - idk.begin() + 1), i};
}
sort(v + 1, v + 2 * n + 1);
for (int i = 1; i <= 2 * n; i++) {
if (v[i].type == 1) {
update(1, 1, 2 * n, v[i].x, dp[v[i].ind]);
}
else {
ans = {0, 0};
query(1, 1, 2 * n, 1, v[i].x);
if (!ans.best) ans.count = 1;
dp[v[i].ind] = {ans.best + 1, ans.count};
}
}
ans = dp[1];
for (int i = 2; i <= n; i++)
ans = ans + dp[i];
cout << ans.best << " " << ans.count;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Partially correct |
1 ms |
340 KB |
Partially correct |
| 4 |
Partially correct |
1 ms |
468 KB |
Partially correct |
| 5 |
Partially correct |
2 ms |
520 KB |
Partially correct |
| 6 |
Partially correct |
3 ms |
724 KB |
Partially correct |
| 7 |
Partially correct |
4 ms |
856 KB |
Partially correct |
| 8 |
Partially correct |
5 ms |
980 KB |
Partially correct |
| 9 |
Partially correct |
10 ms |
1748 KB |
Partially correct |
| 10 |
Runtime error |
21 ms |
5056 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
23 ms |
5200 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
33 ms |
6632 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
35 ms |
7008 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
39 ms |
7652 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
44 ms |
7676 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
45 ms |
7876 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
47 ms |
8224 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
50 ms |
8288 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
49 ms |
8576 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
55 ms |
8776 KB |
Execution killed with signal 11 |
