//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <map>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define maxn 400005
#define mod 30013
using namespace std;
struct obj{
pii a, b;
int val = 0;
obj(int x, int y, int z, int w) {
a.ff = x, a.ss = y, b.ff = z, b.ss = w;
}
};
vector<obj> v;
inline bool cmp(obj p, obj q) {
return p.a.ff < q.a.ff;
}
inline bool cmp2(int i, int j) {
return v[i].b.ff > v[j].b.ff;
}
priority_queue<int, vector<int>, bool(*) (int, int)> pq(cmp2);
int bit[maxn];
void modify(int ind, int val) {
for (;ind < maxn;ind += ind & (-ind)) bit[ind] = max(bit[ind], val);
}
int query(int ind) {
int ret = 0;
for (;ind > 0;ind -= ind & (-ind)) ret = max(ret, bit[ind]);
return ret;
}
int bit2[maxn];
void modify2(int ind, int val) {
for (;ind < maxn;ind += ind & (-ind)) bit2[ind] = (bit2[ind] + val) % mod;
}
int query2(int ind) {
int ret = 0;
for (;ind > 0;ind -= ind & (-ind)) ret = (ret + bit2[ind]) % mod;
return ret;
}
vector<int> lis[100005];
int val[100005];
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n;
cin >> n;
vector<int> num;
for (int i = 0;i < n;i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
v.push_back(obj(c, a, d, b));
num.push_back(a);num.push_back(b);num.push_back(c);num.push_back(d);
}
sort(num.begin(), num.end());
map<int, int> mp;
int cnt = 1;
mp[num[0]] = cnt;
for (int i = 1;i < num.size();i++) {
if (num[i] > num[i - 1]) cnt++;
mp[num[i]] = cnt;
}
for (int i = 0;i < n;i++) {
v[i].a.ss = mp[v[i].a.ss], v[i].b.ss = mp[v[i].b.ss];
v[i].a.ff = mp[v[i].a.ff], v[i].b.ff = mp[v[i].b.ff];
}
sort(v.begin(), v.end(), cmp);
int ans1 = 0, ans2 = 0;
for (int i = 0;i < n;i++) {
while (pq.size() && v[pq.top()].b.ff < v[i].a.ff) {
modify(v[pq.top()].b.ss, v[pq.top()].val);
pq.pop();
}
v[i].val = query(v[i].a.ss - 1) + 1;
lis[v[i].val].push_back(i);
ans1 = max(ans1, v[i].val);
pq.push(i);
}
for (int i = 1;i <= ans1;i++) {
int ind = 0;
for (int j:lis[i]) {
if (i == 1) {
val[j] = 1;
} else {
while (ind < lis[i - 1].size() && v[lis[i - 1][ind]].b.ff < v[j].a.ff) {
modify2(v[lis[i - 1][ind]].b.ss, val[lis[i - 1][ind]]);
ind++;
}
val[j] = query2(v[j].a.ss - 1);
}
}
for (int j = 0;j < ind;j++) modify2(v[lis[i - 1][j]].b.ss, -val[lis[i - 1][j]]);
sort(lis[i].begin(), lis[i].end(), cmp2);
reverse(lis[i].begin(), lis[i].end());
}
for (int j:lis[ans1]) ans2 = (ans2 + val[j]) % mod;
cout << ans1 << " " << ans2 << endl;
}
/*
7
1 3 1 9
4 7 2 8
11 15 4 12
10 12 15 19
16 23 16 22
20 22 13 25
30 31 30 31
*/
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 1;i < num.size();i++) {
| ~~^~~~~~~~~~~~
trapezoid.cpp:96:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | while (ind < lis[i - 1].size() && v[lis[i - 1][ind]].b.ff < v[j].a.ff) {
| ~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2924 KB |
Output is correct |
| 5 |
Correct |
6 ms |
3308 KB |
Output is correct |
| 6 |
Correct |
8 ms |
3564 KB |
Output is correct |
| 7 |
Correct |
9 ms |
3308 KB |
Output is correct |
| 8 |
Correct |
13 ms |
3820 KB |
Output is correct |
| 9 |
Correct |
28 ms |
5192 KB |
Output is correct |
| 10 |
Correct |
46 ms |
5888 KB |
Output is correct |
| 11 |
Correct |
72 ms |
8832 KB |
Output is correct |
| 12 |
Correct |
157 ms |
15352 KB |
Output is correct |
| 13 |
Correct |
186 ms |
16888 KB |
Output is correct |
| 14 |
Correct |
225 ms |
20080 KB |
Output is correct |
| 15 |
Correct |
246 ms |
18928 KB |
Output is correct |
| 16 |
Correct |
278 ms |
19952 KB |
Output is correct |
| 17 |
Correct |
285 ms |
23152 KB |
Output is correct |
| 18 |
Correct |
235 ms |
16752 KB |
Output is correct |
| 19 |
Correct |
293 ms |
24432 KB |
Output is correct |
| 20 |
Correct |
330 ms |
25456 KB |
Output is correct |
