#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
using namespace std;
long n, dp[100005], dp2[100005], maxa[700000] = {}, suma[700000] = {};
void updf(long i, long s, long e, long v, long dm, long ds) {
if (s > v || e < v) {
return;
} if (s == e && s == v) {
maxa[i] = dm; suma[i] = ds;
return;
}
updf(2*i+1, s, (s+e)/2, v, dm, ds);
updf(2*i+2, (s+e)/2+1, e, v, dm, ds);
if (maxa[2*i+1] > maxa[2*i+2]){
maxa[i] = maxa[2*i+1], suma[i] = suma[2*i+1];
} else if (maxa[2*i+1] == maxa[2*i+2]){
maxa[i] = maxa[2*i+1], suma[i] = suma[2*i+1]+suma[2*i+2] % 30013;
} else {
maxa[i] = maxa[2*i+2], suma[i] = suma[2*i+2];
}
}
void updh(long ind, long dm, long ds) {
long a = 0, b = 0; updf(a, b, n-1, ind, dm, ds);
}
pair<long, long> qf(long i, long s, long e, long l, long u) {
if (s > e || s > u || e < l) {
return make_pair(-1000, 0);
}
if (s >= l && e <= u) {
return make_pair(maxa[i], suma[i]);
}
pair<long, long> a = qf(2*i+1, s, (s+e)/2, l, u), b = qf(2*i+2, (s+e)/2+1, e, l, u);
if (a.first > b.first){
return a;
} else if (a.first < b.first){
return b;
} else {
return make_pair(a.first, a.second+b.second%30013);
}
}
pair<long, long> qh(long l, long u) {
long a = 0, b = 0; return qf(a, b, n-1, l, u);
}
struct trap {
long a, b, c, d, i;
trap(long i1, long i2, long i3, long i4){
a = i1; b = i2; c = i3; d = i4; i = 0;
}
};
bool comp1 (trap t1, trap t2){
return t1.a < t2.a;
}
struct comp2 {
bool operator()(trap t1, trap t2){
return t1.b > t2.b;
}
};
vector<long> cc; unordered_map<long, long> ccm;
vector<trap> pqa;
priority_queue<trap, vector<trap>, comp2> pqb;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (long i = 0; i < n; i++){
long i1, i2, i3, i4;
cin >> i1 >> i2 >> i3 >> i4;
cc.push_back(i3); cc.push_back(i4);
pqa.push_back(trap(i1, i2, i3, i4));
}
sort(cc.begin(), cc.end());
for (int i = 0; i < 2*n; i++){
ccm.insert(make_pair(cc[i], i));
}
sort(pqa.begin(), pqa.end(), comp1);
for (long i = 0; i < n; i++){
pqa[i].i = i; pqa[i].c = ccm[pqa[i].c]+1; pqa[i].d = ccm[pqa[i].d]+1;
}
n = 2*n+1; updh(0, 0, 1);
for (long i = 0; i < pqa.size(); i++){
while (pqb.size() > 0 && pqb.top().b < pqa[i].a){
updh(pqb.top().d, dp[pqb.top().i], dp2[pqb.top().i]); pqb.pop();
}
pair<long, long> temp = qh(0, pqa[i].c);
dp[i] = temp.first+1; dp2[i] = temp.second;
pqb.push(pqa[i]);
}
while (pqb.size() > 0){
updh(pqb.top().d, dp[pqb.top().i], dp2[pqb.top().i]); pqb.pop();
}
pair<long, long> ans = qh(0, n-1);
cout << ans.first % 30013 << " " << ans.second % 30013 << endl;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:95:21: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<trap>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (long i = 0; i < pqa.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
512 KB |
Output is correct |
| 4 |
Correct |
2 ms |
640 KB |
Output is correct |
| 5 |
Correct |
5 ms |
896 KB |
Output is correct |
| 6 |
Correct |
8 ms |
1152 KB |
Output is correct |
| 7 |
Correct |
7 ms |
1408 KB |
Output is correct |
| 8 |
Correct |
9 ms |
1756 KB |
Output is correct |
| 9 |
Correct |
17 ms |
3096 KB |
Output is correct |
| 10 |
Correct |
36 ms |
5768 KB |
Output is correct |
| 11 |
Correct |
45 ms |
6276 KB |
Output is correct |
| 12 |
Correct |
99 ms |
12412 KB |
Output is correct |
| 13 |
Correct |
116 ms |
13696 KB |
Output is correct |
| 14 |
Correct |
155 ms |
20208 KB |
Output is correct |
| 15 |
Correct |
159 ms |
21236 KB |
Output is correct |
| 16 |
Correct |
174 ms |
22260 KB |
Output is correct |
| 17 |
Correct |
190 ms |
23024 KB |
Output is correct |
| 18 |
Correct |
167 ms |
22644 KB |
Output is correct |
| 19 |
Correct |
196 ms |
22516 KB |
Output is correct |
| 20 |
Correct |
214 ms |
24056 KB |
Output is correct |
