#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct obj{
ll v,c;
obj(): v(0),c(1){}
obj(ll a, ll b): v(a), c(b){}
obj operator+(const obj &o) const{
return v==o.v?obj(v,c+o.c):v<o.v?o:*this;
}
obj operator|(const obj &o) const{
return v==o.v?obj(v,max(c,o.c)):v<o.v?o:*this;
}
};
struct segtree{
ll n;
vector<obj> dat;
vector<obj> tag;
segtree(ll N): n(N){
dat.resize(n<<2);
tag.resize(n<<2,obj(0,0));
}
void add(ll i, obj v){
dat[i] = dat[i]+v;
tag[i] = tag[i]+v;
}
void push(ll i){
add(i<<1,tag[i]);
add(i<<1|1,tag[i]);
tag[i] = obj(0,0);
}
void add(ll i, ll l, ll r, ll ql, ll qr, obj v){
if (ql<=l&&r<=qr){
add(i,v);
}else{
ll m = l+r>>1;
push(i);
if (ql<=m) add(i<<1,l,m,ql,qr,v);
if (qr>m) add(i<<1|1,m+1,r,ql,qr,v);
}
}
void add(ll ql, ll qr, obj v){
add(1,0,n-1,ql,qr,v);
}
obj query(ll i, ll l, ll r, ll x){
if (l == r){
return dat[i];
}else{
ll m = l+r>>1;
push(i);
if (x<=m) return query(i<<1,l,m,x);
else return query(i<<1|1,m+1,r,x);
}
}
obj query(ll x){
if (x<0) return obj(0,1);
return query(1,0,n-1,x);
}
};
struct evt{
ll a,b,c,d;
bool operator<(const evt &o) const{
return b>o.b;
}
};
int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll n;
cin >> n;
vector<evt> a(n);
for(auto &o : a) cin >> o.a >> o.b >> o.c >> o.d;
sort(a.begin(),a.end(),[&](const evt &a, const evt &b){return a.a<b.a;});
vector<ll> x;
for(auto &o : a) x.push_back(o.a),x.push_back(o.b),x.push_back(o.c),x.push_back(o.d);
sort(x.begin(),x.end());
x.resize(unique(x.begin(),x.end())-x.begin());
auto gx = [&](ll i){return lower_bound(x.begin(),x.end(),i)-x.begin();};
segtree t(x.size());
obj ans = obj(0,1);
priority_queue<evt> q;
for(evt o : a){
while (!q.empty()&&q.top().b<o.a){
evt z = q.top();
q.pop();
t.add(gx(z.d),x.size()-1,obj(z.a,z.c));
}
obj g = t.query(gx(o.c)-1);
g = obj(g.v+1,g.c);
ans = ans | g;
q.push({g.v,o.b,g.c,o.d});
}
cout << ans.v << " " << ans.c << '\n';
}
Compilation message
trapezoid.cpp: In member function 'void segtree::add(ll, ll, ll, ll, ll, obj)':
trapezoid.cpp:36:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | ll m = l+r>>1;
| ~^~
trapezoid.cpp: In member function 'obj segtree::query(ll, ll, ll, ll)':
trapezoid.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | ll m = l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
212 KB |
Partially correct |
| 2 |
Partially correct |
1 ms |
316 KB |
Partially correct |
| 3 |
Incorrect |
1 ms |
468 KB |
Expected int32, but "3389517342720" found |
| 4 |
Incorrect |
1 ms |
596 KB |
Expected int32, but "7117945929880436736" found |
| 5 |
Partially correct |
3 ms |
1492 KB |
Partially correct |
| 6 |
Incorrect |
5 ms |
2132 KB |
Expected int32, but "3505721401087858624" found |
| 7 |
Incorrect |
6 ms |
1744 KB |
Expected int32, but "7714248878884782080" found |
| 8 |
Partially correct |
8 ms |
2732 KB |
Partially correct |
| 9 |
Incorrect |
17 ms |
5844 KB |
Expected int32, but "522405817371529289" found |
| 10 |
Incorrect |
29 ms |
7268 KB |
Expected int32, but "7012317025184523008" found |
| 11 |
Incorrect |
48 ms |
13972 KB |
Expected int32, but "8326539073436363494" found |
| 12 |
Incorrect |
94 ms |
28608 KB |
Expected int32, but "8737773565241323904" found |
| 13 |
Incorrect |
114 ms |
32980 KB |
Expected int32, but "-4195152448689438272" found |
| 14 |
Incorrect |
151 ms |
40360 KB |
Expected int32, but "7908491273097169920" found |
| 15 |
Incorrect |
154 ms |
36816 KB |
Expected int32, but "9069179206125513728" found |
| 16 |
Incorrect |
165 ms |
39492 KB |
Expected int32, but "1077624591058923776" found |
| 17 |
Incorrect |
171 ms |
46756 KB |
Expected int32, but "9078516102168694496" found |
| 18 |
Incorrect |
125 ms |
31112 KB |
Expected int32, but "8603867276704155842" found |
| 19 |
Incorrect |
171 ms |
50124 KB |
Expected int32, but "9168401195073447936" found |
| 20 |
Incorrect |
209 ms |
51420 KB |
Expected int32, but "9205429944092974250" found |
