#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 1e5 + 5;
const int MOD = 30013;
int add (int a, int b) { return a + b - (a + b < MOD ? 0 : MOD); }
struct getMax {
int best, cnt;
getMax() : best(0), cnt(0) {}
getMax (int a, int b) : best(a), cnt(b) {}
void push (int cur) {
if (cur > best) best = cur, cnt = 1;
else if (cur == best) cnt = add(cnt, 1);
}
getMax operator + (const getMax &o) const {
if (best == o.best) return getMax(best, add(cnt, o.cnt));
return (best > o.best ? *this : o);
}
};
struct IT {
vector<getMax> tr;
IT (int sz) : tr(4 * sz) {}
void update (int pos, getMax val, int k, int l, int r) {
for (; l < r;) {
int mid = (l + r) >> 1;
if (pos <= mid) k <<= 1, r = mid;
else k <<= 1, k |= 1, l = mid + 1;
}
tr[k] = tr[k] + val;
for (k /= 2; k; k /= 2)
tr[k] = tr[2 * k] + tr[2 * k + 1];
}
getMax query (int a, int b, int k, int l, int r) {
if (b < l || r < a) return getMax();
if (a <= l && r <= b) return tr[k];
int mid = (l + r) >> 1;
return query(a, b, 2 * k, l, mid) + query(a, b, 2 * k + 1, mid + 1, r);
}
};
struct item {
int a, b, c, d;
item() : a(a), b(b), c(c), d(d) {}
item (int a, int b, int c, int d) : a(a), b(b), c(c), d(d) {}
bool operator < (const item &o) const { return a < o.a; }
friend istream& operator >> (istream &inp, item &i) {
return inp >> i.a >> i.b >> i.c >> i.d, inp;
}
} trapezoid[mn];
vector<int> cmp;
getMax dp[mn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
for (int i = 0; i < n; i++) {
cin >> trapezoid[i];
cmp.push_back(trapezoid[i].c), cmp.push_back(trapezoid[i].d);
}
sort(trapezoid, trapezoid + n);
sort(all(cmp)), filter(cmp);
for (int i = 0; i < n; i++) {
trapezoid[i].c = lower_bound(all(cmp), trapezoid[i].c) - cmp.begin();
trapezoid[i].d = lower_bound(all(cmp), trapezoid[i].d) - cmp.begin();
}
priority_queue<pii> wait;
IT tree(cmp.size());
for (int i = 0; i < n; i++) {
while (wait.size() && -wait.top().first < trapezoid[i].a) {
int j = wait.top().second; wait.pop();
tree.update(trapezoid[j].d, dp[j], 1, 0, cmp.size() - 1);
}
dp[i] = tree.query(0, trapezoid[i].c - 1, 1, 0, cmp.size() - 1);
dp[i].best++, dp[i].push(1);
wait.emplace(-trapezoid[i].b, i);
}
getMax ans;
for (int i = 0; i < n; i++) ans = ans + dp[i];
cout << ans.best << " " << ans.cnt << "\n";
return 0;
}
Compilation message
trapezoid.cpp: In constructor 'item::item()':
trapezoid.cpp:61:5: warning: 'item::a' is initialized with itself [-Winit-self]
61 | item() : a(a), b(b), c(c), d(d) {}
| ^~~~
trapezoid.cpp:61:5: warning: 'item::b' is initialized with itself [-Winit-self]
trapezoid.cpp:61:5: warning: 'item::c' is initialized with itself [-Winit-self]
trapezoid.cpp:61:5: warning: 'item::d' is initialized with itself [-Winit-self]
trapezoid.cpp: In constructor 'item::item()':
trapezoid.cpp:61:16: warning: '*<unknown>.item::a' is used uninitialized in this function [-Wuninitialized]
61 | item() : a(a), b(b), c(c), d(d) {}
| ^
trapezoid.cpp:61:22: warning: '*<unknown>.item::b' is used uninitialized in this function [-Wuninitialized]
61 | item() : a(a), b(b), c(c), d(d) {}
| ^
trapezoid.cpp:61:28: warning: '*<unknown>.item::c' is used uninitialized in this function [-Wuninitialized]
61 | item() : a(a), b(b), c(c), d(d) {}
| ^
trapezoid.cpp:61:34: warning: '*<unknown>.item::d' is used uninitialized in this function [-Wuninitialized]
61 | item() : a(a), b(b), c(c), d(d) {}
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2640 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2640 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2656 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2808 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2640 KB |
Output is correct |
| 6 |
Correct |
4 ms |
3068 KB |
Output is correct |
| 7 |
Correct |
5 ms |
2896 KB |
Output is correct |
| 8 |
Correct |
6 ms |
3156 KB |
Output is correct |
| 9 |
Correct |
10 ms |
3664 KB |
Output is correct |
| 10 |
Correct |
17 ms |
4544 KB |
Output is correct |
| 11 |
Correct |
28 ms |
5076 KB |
Output is correct |
| 12 |
Correct |
46 ms |
7572 KB |
Output is correct |
| 13 |
Correct |
59 ms |
8408 KB |
Output is correct |
| 14 |
Correct |
66 ms |
9704 KB |
Output is correct |
| 15 |
Correct |
72 ms |
9924 KB |
Output is correct |
| 16 |
Correct |
80 ms |
9324 KB |
Output is correct |
| 17 |
Correct |
83 ms |
10948 KB |
Output is correct |
| 18 |
Correct |
76 ms |
11348 KB |
Output is correct |
| 19 |
Correct |
87 ms |
11972 KB |
Output is correct |
| 20 |
Correct |
98 ms |
12480 KB |
Output is correct |
