#include <bits/stdc++.h>
typedef long long int ll;
#define INF ll(1e12 + 7)
#define INF2 998244353
#define N (ll)(2e5 + 5)
using namespace std;
#define int ll
#define lsb(x) (x & (-x))
int n, g, h,m, q,z,t1,t2, ans, ans2;
map<int, pair<int, int>> c;
pair<pair<int, int>, pair<int, int>> p[N];
vector<pair<pair<int, int>, pair<int, int>>> v;
vector<int> v2;
pair<int, int> comb(pair<int, int> x, pair<int, int> y){
if(x.first > y.first){
return x;
}
else if(x.first < y.first){
return y;
}
else{
return {x.first, x.second + y.second};
}
}
struct SegTree{
int n;
vector<pair<int, int>> tree;
SegTree(int _n){
n = _n+1;
while(lsb(n) != n)
n += lsb(n);
tree.resize(2*n, {0, 0});
}
void update(int i, pair<int, int> val){
i += n;
tree[i] = val;
while(i >>= 1){
tree[i] = comb(tree[i * 2] , tree[i * 2 + 1]);
}
}
pair<int, int> query(int ql, int qr){ return query(1, 0, n-1, ql, qr); }
pair<int, int> query(int i, int lb, int rb, int ql, int qr){
if(ql <= lb && rb <= qr){
return tree[i];
}
if(qr < lb || rb < ql)
return {0, 0};
int md = (lb+rb)/2;
return comb(query(2*i, lb, md, ql, qr) , query(2*i+1, md+1, rb, ql, qr));
}
};
void solve(){
cin >> n;
SegTree s(N * 2);
for(int i=1; i<=n; i++){
cin >> p[i].first.first >> p[i].first.second >> p[i].second.first >> p[i].second.second;
v.push_back({{p[i].second.first, 0}, {p[i].first.first, p[i].first.second}});
v.push_back({{p[i].second.second, 1}, {p[i].first.first, p[i].first.second}});
v2.push_back(p[i].first.first);
v2.push_back(p[i].first.second);
v2.push_back(p[i].second.first);
v2.push_back(p[i].second.second);
}
v2.push_back(0);
v2.push_back(1);
sort(v2.begin(), v2.end());
unique(v2.begin(), v2.end());
for(int i=0; i<v.size(); i++){
v[i].first.first = 1 + (lower_bound(v2.begin(), v2.end(), v[i].first.first) - v2.begin());
v[i].second.first = 1 + (lower_bound(v2.begin(), v2.end(), v[i].second.first) - v2.begin());
v[i].second.second = 1 + (lower_bound(v2.begin(), v2.end(), v[i].second.second) - v2.begin());
}
sort(v.begin(), v.end());
for(int i=0; i<v.size(); i++){
if(v[i].first.second){
g = c[v[i].second.first].first, h = c[v[i].second.first].second;
s.update(v[i].second.second, {g, h});
}
else{
pair<int, int> p2 = s.query(0ll, v[i].second.first - 1);
g = p2.first, h = p2.second;
g++;
if(g > ans){
ans = g;
ans2 = h;
}
if(h==0)h=1;
c[v[i].second.first] = {g, h};
}
}
cout << ans << " " << ans2;
}
signed main(){
freopen("trapezoid.in", "r", stdin);
freopen("trapezoid.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
//cin>>T;
while (T--){
solve();
}
}
Compilation message
trapezoid.cpp: In function 'void solve()':
trapezoid.cpp:79:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i=0; i<v.size(); i++){
| ~^~~~~~~~~
trapezoid.cpp:86:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i=0; i<v.size(); i++){
| ~^~~~~~~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:108:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | freopen("trapezoid.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp:109:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | freopen("trapezoid.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
16724 KB |
Unexpected end of file - int32 expected |
| 2 |
Incorrect |
11 ms |
16724 KB |
Unexpected end of file - int32 expected |
| 3 |
Incorrect |
9 ms |
16724 KB |
Unexpected end of file - int32 expected |
| 4 |
Incorrect |
8 ms |
16736 KB |
Unexpected end of file - int32 expected |
| 5 |
Incorrect |
8 ms |
16724 KB |
Unexpected end of file - int32 expected |
| 6 |
Incorrect |
9 ms |
16724 KB |
Unexpected end of file - int32 expected |
| 7 |
Incorrect |
8 ms |
16724 KB |
Unexpected end of file - int32 expected |
| 8 |
Incorrect |
9 ms |
16728 KB |
Unexpected end of file - int32 expected |
| 9 |
Incorrect |
8 ms |
16724 KB |
Unexpected end of file - int32 expected |
| 10 |
Incorrect |
8 ms |
16820 KB |
Unexpected end of file - int32 expected |
| 11 |
Incorrect |
9 ms |
16736 KB |
Unexpected end of file - int32 expected |
| 12 |
Incorrect |
9 ms |
16724 KB |
Unexpected end of file - int32 expected |
| 13 |
Incorrect |
8 ms |
16724 KB |
Unexpected end of file - int32 expected |
| 14 |
Incorrect |
8 ms |
16724 KB |
Unexpected end of file - int32 expected |
| 15 |
Incorrect |
12 ms |
16724 KB |
Unexpected end of file - int32 expected |
| 16 |
Incorrect |
10 ms |
16796 KB |
Unexpected end of file - int32 expected |
| 17 |
Incorrect |
9 ms |
16808 KB |
Unexpected end of file - int32 expected |
| 18 |
Incorrect |
11 ms |
16792 KB |
Unexpected end of file - int32 expected |
| 19 |
Incorrect |
9 ms |
16736 KB |
Unexpected end of file - int32 expected |
| 20 |
Incorrect |
9 ms |
16724 KB |
Unexpected end of file - int32 expected |
