#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 30013;
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)%mod):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});
}
while (!q.empty()){
evt z = q.top();
q.pop();
t.add(gx(z.d),x.size()-1,obj(z.a,z.c));
}
ans = t.query(x.size()-1);
cout << ans.v << " " << (ans.c%mod) << '\n';
}
Compilation message
trapezoid.cpp: In member function 'void segtree::add(ll, ll, ll, ll, ll, obj)':
trapezoid.cpp:37:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | ll m = l+r>>1;
| ~^~
trapezoid.cpp: In member function 'obj segtree::query(ll, ll, ll, ll)':
trapezoid.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | ll m = l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1364 KB |
Output is correct |
| 6 |
Correct |
5 ms |
2004 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1620 KB |
Output is correct |
| 8 |
Correct |
8 ms |
2520 KB |
Output is correct |
| 9 |
Correct |
17 ms |
5640 KB |
Output is correct |
| 10 |
Correct |
26 ms |
6848 KB |
Output is correct |
| 11 |
Correct |
44 ms |
13420 KB |
Output is correct |
| 12 |
Correct |
92 ms |
27316 KB |
Output is correct |
| 13 |
Correct |
119 ms |
31372 KB |
Output is correct |
| 14 |
Correct |
144 ms |
38472 KB |
Output is correct |
| 15 |
Correct |
154 ms |
34768 KB |
Output is correct |
| 16 |
Correct |
188 ms |
37368 KB |
Output is correct |
| 17 |
Correct |
176 ms |
44436 KB |
Output is correct |
| 18 |
Correct |
125 ms |
28728 KB |
Output is correct |
| 19 |
Correct |
187 ms |
47564 KB |
Output is correct |
| 20 |
Correct |
211 ms |
48776 KB |
Output is correct |
