#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
#define int long long
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int a[N][5], n;
map<int,int> id;
pii tree[4 * N], dp[N];
void compress(vector<int> x) {
sort(x.begin() ,x.end());
int idx = 0;
for(int i = 0; i < x.size(); i++) {
if(!i || x[i] != x[i - 1]) idx++;
id[x[i]] = idx;
}
}
pii merge(pii a, pii b) {
if(a.f == b.f) return {a.f, a.s + b.s};
return max(a, b);
}
void upd(int u,int ind,int l,int r, pii a) {
if(l > ind || r < ind) return;
if(l == r) {
tree[u] = a;
return;
}
int mid = (l + r)/2;
upd(2 * u, ind, l, mid, a); upd(2 * u + 1, ind, mid + 1, r, a);
tree[u] = merge(tree[2 * u], tree[2 * u + 1]);
}
pii get(int u,int st,int en,int l,int r) {
if(l > en || r < st) return {0, 0};
if(st <= l && r <= en) return tree[u];
int mid = (l + r)/2;
return merge(get(2 * u, st, en, l, mid), get(2 * u + 1,st,en, mid + 1, r));
}
main() {
cin >> n;
vector<int> x;
vector<pair<int,pii> > y;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 4; j++) cin >> a[i][j];
x.push_back(a[i][2]);
x.push_back(a[i][3]);
y.push_back({a[i][0], {i, 0}});
y.push_back({a[i][1], {i, 1}});
}
compress(x);
sort(y.begin(), y.end());
for(int i = 0; i < y.size(); i++) {
int idx = y[i].s.f;
if(y[i].s.s == 0) {
dp[idx] = get(1, 1, id[a[idx][2]] - 1, 1, 2 * n);
dp[idx].f++;
if(dp[idx].f == 1) dp[idx].s = 1;
}
else upd(1, id[a[idx][3]],1, 2 * n, dp[idx]);
}
cout << tree[1].f <<" " << tree[1].s;
}
Compilation message
trapezoid.cpp: In function 'void compress(std::vector<long long int>)':
trapezoid.cpp:14:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int i = 0; i < x.size(); i++) {
| ~~^~~~~~~~~~
trapezoid.cpp: At global scope:
trapezoid.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
39 | main() {
| ^~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:52:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i = 0; i < y.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
460 KB |
Expected int32, but "10313130667392" found |
| 4 |
Incorrect |
2 ms |
588 KB |
Expected int32, but "-8550276992825950208" found |
| 5 |
Partially correct |
5 ms |
972 KB |
Partially correct |
| 6 |
Incorrect |
7 ms |
1360 KB |
Expected int32, but "-8629080777422869056" found |
| 7 |
Incorrect |
9 ms |
1704 KB |
Expected int32, but "-3319866744691032064" found |
| 8 |
Partially correct |
14 ms |
2164 KB |
Partially correct |
| 9 |
Incorrect |
34 ms |
4128 KB |
Expected int32, but "2248786528710863832" found |
| 10 |
Incorrect |
52 ms |
8000 KB |
Expected int32, but "-5022802232222890496" found |
| 11 |
Incorrect |
62 ms |
9164 KB |
Expected int32, but "-1298419000938405298" found |
| 12 |
Incorrect |
199 ms |
18588 KB |
Expected int32, but "9183932486774365824" found |
| 13 |
Incorrect |
177 ms |
21428 KB |
Expected int32, but "-4195152448689438272" found |
| 14 |
Incorrect |
224 ms |
28248 KB |
Expected int32, but "-3175106568905838848" found |
| 15 |
Incorrect |
227 ms |
29864 KB |
Expected int32, but "-8026369531311511552" found |
| 16 |
Incorrect |
286 ms |
31156 KB |
Expected int32, but "6233362917342126368" found |
| 17 |
Incorrect |
285 ms |
32764 KB |
Expected int32, but "-7505826292837535760" found |
| 18 |
Incorrect |
215 ms |
33836 KB |
Expected int32, but "-6197299359079266322" found |
| 19 |
Incorrect |
256 ms |
33972 KB |
Expected int32, but "5619696618904563712" found |
| 20 |
Incorrect |
329 ms |
36448 KB |
Expected int32, but "-335818733633578353" found |
