//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
int n;
int ind[100001][2];
int mod=30013;
pair<int,int> dp[100001];
pair<int,int> re(pair<int,int> aa,pair<int,int> bb){
if(aa.a>bb.a){
return aa;
}
if(aa.a<bb.a){
return bb;
}
return {aa.a,(aa.b+bb.b)%mod};
}
pair<int,int> tree[100001*8];
void update(int no,int l,int r,int i,pair<int,int> val){
if(l==r){
tree[no]=val;
}
else{
int mid=(l+r)/2;
if(i<=mid){
update(no*2+1,l,mid,i,val);
}
else{
update(no*2+2,mid+1,r,i,val);
}
tree[no]=re(tree[no*2+1],tree[no*2+2]);
}
}
pair<int,int> query(int no,int l,int r,int aa,int bb){
if(aa>bb or l>bb or r<aa){
return {0,0};
}
if(aa<=l and r<=bb){
//cout<<l<<"//"<<r<<","<<tree[no].a<<","<<tree[no].b<<endl;
return tree[no];
}
int mid=(l+r)/2;
return re(query(no*2+1,l,mid,aa,bb),query(no*2+2,mid+1,r,aa,bb));
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
vector<pair<int,pair<int,int>>> ss;
vector<pair<int,pair<int,int>>> tt;
for(int i=0;i<n;i++){
int aa,bb,cc,dd;
cin>>aa>>bb>>cc>>dd;
ss.pb({aa,{i,0}});
ss.pb({bb,{i,1}});
tt.pb({cc,{i,0}});
tt.pb({dd,{i,1}});
}
for(int i=0;i<8*n;i++){
tree[i]={0,0};
}
sort(ss.begin(),ss.end());
for(int i=0;i<2*n;i++){
ind[ss[i].b.a][ss[i].b.b]=i;
}
sort(tt.begin(),tt.end());
pair<int,int> ma={0,0};
for(auto j:tt){
if(j.b.b==0){
// cout<<ind[j.b.a][0]-1<<endl;
pair<int,int> xx=query(0,0,2*n-1,0,ind[j.b.a][0]-1);
xx.a+=1;
// cout<<endl;
if(xx.b==0){
xx.b=1;
}
dp[j.b.a]=xx;
ma=re(ma,dp[j.b.a]);
// cout<<j.b.a<<":"<<xx.a<<":"<<xx.b<<endl;
}
else{
update(0,0,2*n-1,ind[j.b.a][1],dp[j.b.a]);
//cout<<ind[j.b.a][1]<<",,,"<<j.b.a<<endl;
}
}
cout<<ma.a<<" "<<ma.b<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
2 ms |
492 KB |
Output is correct |
| 5 |
Correct |
3 ms |
748 KB |
Output is correct |
| 6 |
Correct |
4 ms |
876 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1004 KB |
Output is correct |
| 8 |
Correct |
8 ms |
1260 KB |
Output is correct |
| 9 |
Correct |
13 ms |
2020 KB |
Output is correct |
| 10 |
Correct |
24 ms |
3548 KB |
Output is correct |
| 11 |
Correct |
34 ms |
4316 KB |
Output is correct |
| 12 |
Correct |
71 ms |
8148 KB |
Output is correct |
| 13 |
Correct |
84 ms |
9556 KB |
Output is correct |
| 14 |
Correct |
99 ms |
11208 KB |
Output is correct |
| 15 |
Correct |
113 ms |
11848 KB |
Output is correct |
| 16 |
Correct |
117 ms |
12616 KB |
Output is correct |
| 17 |
Correct |
124 ms |
13512 KB |
Output is correct |
| 18 |
Correct |
111 ms |
14152 KB |
Output is correct |
| 19 |
Correct |
129 ms |
14920 KB |
Output is correct |
| 20 |
Correct |
143 ms |
15688 KB |
Output is correct |
