#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
struct SegTree {
int n;
vector<pii> tree;
SegTree(int _n) : n(_n), tree(4*_n, {0, 0}) {}
pii merge(pii a, pii b) {
if(a.first > b.first) return a;
if(a.first < b.first) return b;
return { a.first, a.second + b.second };
}
void update(int u, int tl, int tr, int p, int v, int w) {
if(tl == tr) {
tree[u] = merge(tree[u], { v, w });
} else {
int tm = (tl + tr) / 2;
if(p <= tm) update(2*u, tl, tm, p, v, w);
else update(2*u+1, tm+1, tr, p, v, w);
tree[u] = merge(tree[2*u], tree[2*u+1]);
}
}
pii query(int u, int tl, int tr, int l, int r) {
if(l > tr || tl > r) return { 0, 0 };
if(l <= tl && tr <= r) return tree[u];
int tm = (tl + tr) / 2;
return merge(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
}
void update(int p, int v, int w) { update(1, 0, n-1, p, v, w); }
pii query(int l, int r) { return query(1, 0, n-1, l, r); }
};
signed main() {
ios_base::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
int n; cin >> n;
vector<array<int, 4> > v(n);
set<int> s;
for(int i=0; i<n; i++) {
for(int j=0; j<4; j++) cin >> v[i][j];
for(int j=0; j<4; j++) s.insert(v[i][j]);
}
vector<int> comp(s.begin(), s.end());
sort(v.begin(), v.end());
for(int i=0; i<n; i++)
for(int j=0; j<4; j++) v[i][j] = lower_bound(comp.begin(), comp.end(), v[i][j]) - comp.begin();
vector<pii> dp(n);
SegTree tree(comp.size());
priority_queue<pii> pq;
for(int i=0; i<n; i++) {
dp[i] = { 1, 1 };
while(!pq.empty() && pq.top().first < v[i][0]) {
tree.update(v[pq.top().second][3], dp[pq.top().second].first, dp[pq.top().second].second);
pq.pop();
}
auto res = tree.query(0, v[i][2]-1);
if(res.first) dp[i] = { res.first + 1, res.second };
pq.push({ v[i][1], i });
}
while(!pq.empty()) {
tree.update(v[pq.top().second][3], dp[pq.top().second].first, dp[pq.top().second].second);
pq.pop();
}
auto [mx, ways] = tree.query(0, comp.size() - 1);
cout << mx << " " << ways << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
360 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
360 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
360 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
616 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
1128 KB |
Output isn't correct |
| 6 |
Incorrect |
4 ms |
1368 KB |
Output isn't correct |
| 7 |
Incorrect |
4 ms |
1372 KB |
Output isn't correct |
| 8 |
Incorrect |
8 ms |
1880 KB |
Output isn't correct |
| 9 |
Incorrect |
17 ms |
4188 KB |
Output isn't correct |
| 10 |
Incorrect |
23 ms |
4956 KB |
Output isn't correct |
| 11 |
Incorrect |
45 ms |
9392 KB |
Output isn't correct |
| 12 |
Incorrect |
95 ms |
18908 KB |
Output isn't correct |
| 13 |
Incorrect |
115 ms |
21720 KB |
Output isn't correct |
| 14 |
Incorrect |
142 ms |
26996 KB |
Output isn't correct |
| 15 |
Incorrect |
158 ms |
24356 KB |
Output isn't correct |
| 16 |
Incorrect |
178 ms |
26060 KB |
Output isn't correct |
| 17 |
Incorrect |
184 ms |
30668 KB |
Output isn't correct |
| 18 |
Incorrect |
117 ms |
20700 KB |
Output isn't correct |
| 19 |
Incorrect |
180 ms |
32372 KB |
Output isn't correct |
| 20 |
Incorrect |
205 ms |
33916 KB |
Output isn't correct |
