#include<bits/stdc++.h>
using namespace std;
#define scl(x) scanf("%lld",&x)
#define sc(x) scanf("%d",&x)
#define ll long long
#define lop(i,n) for(int i=0;i<n;++i)
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
const int mod=30013;
int add(int a,int b){
a+=b;
if(a>=mod)a-=mod;
return a;
}
const int N=1e5+100,LG=24;
ii tree[N*LG];
int L[N*LG],R[N*LG],ne;
ii dp[N];
void build(int root,int s,int e){
if(s==e)return;
L[root]=ne++;
R[root]=ne++;
int m=s+((e-s)>>1);
build(L[root],s,m);
build(R[root],m+1,e);
}
ii merge(ii a,ii b){
if(a.first>b.first)return a;
if(b.first>a.first)return b;
return ii(a.first,add(a.second,b.second));
}
void upd(int nroot,int root,int s,int e,int i,ii val){
if(s==e){
tree[nroot]=merge(tree[root],val);
return;
}
int m=s+((e-s)>>1);
if(i<=m){
L[nroot]=ne++;
R[nroot]=R[root];
upd(L[nroot],L[root],s,m,i,val);
}
else {
L[nroot]=L[root];
R[nroot]=ne++;
upd(R[nroot],R[root],m+1,e,i,val);
}
tree[nroot]=merge(tree[L[nroot]],tree[R[nroot]]);
}
ii get(int root,int s,int e,int l,int r){
if(e<l||s>r)return ii(0,0);
if(s>=l&&e<=r)return tree[root];
int m=s+((e-s)>>1);
return merge(get(L[root],s,m,l,r),get(R[root],m+1,e,l,r));
}
struct node{
int a,b,c,d;
bool operator<(const node &o)const{
return a<o.a;
}
}arr[N];
int n;
vector<int> uncom;
int roots[N];
int main(){
#ifndef ONLINE_JUDGE
//freopen("i.txt","r",stdin);
#endif
sc(n);
lop(i,n){
sc(arr[i].a),sc(arr[i].b);
sc(arr[i].c),sc(arr[i].d);
uncom.push_back(arr[i].c);
}
uncom.push_back(1e9+1);
sort(uncom.begin(),uncom.end());
uncom.erase(unique(uncom.begin(),uncom.end()),uncom.end());
lop(i,n){
arr[i].c=lower_bound(uncom.begin(),uncom.end(),arr[i].c)-uncom.begin();
arr[i].d=upper_bound(uncom.begin(),uncom.end(),arr[i].d)-uncom.begin();
}
sort(arr,arr+n);
roots[n+1]=ne++;
build(roots[n+1],0,uncom.size()-1);
arr[n].a=1e9+1;
upd(roots[n],roots[n+1],0,uncom.size()-1,uncom.size()-1,ii(0,1));
for(int i=n-1;i>=0;i--){
node qr;
qr.a=arr[i].b;
int start=upper_bound(arr+i+1,arr+n+1,qr)-arr;
dp[i]=get(roots[start],0,uncom.size()-1,arr[i].d,uncom.size()-1);
if(!dp[i].first)dp[i].second=1;
dp[i].first++;
roots[i]=ne++;
upd(roots[i],roots[i+1],0,uncom.size()-1,arr[i].c,dp[i]);
}
ii out(0,0);
lop(i,n)
out=merge(out,dp[i]);
printf("%d %d\n",out.first,out.second);
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#define sc(x) scanf("%d",&x)
~~~~~^~~~~~~~~
trapezoid.cpp:76:2: note: in expansion of macro 'sc'
sc(n);
^~
trapezoid.cpp:78:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
sc(arr[i].a),sc(arr[i].b);
^
trapezoid.cpp:78:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
trapezoid.cpp:79:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
sc(arr[i].c),sc(arr[i].d);
^
trapezoid.cpp:79:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
444 KB |
Output is correct |
| 3 |
Correct |
2 ms |
548 KB |
Output is correct |
| 4 |
Correct |
3 ms |
548 KB |
Output is correct |
| 5 |
Correct |
4 ms |
928 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1224 KB |
Output is correct |
| 7 |
Correct |
7 ms |
1480 KB |
Output is correct |
| 8 |
Correct |
10 ms |
1784 KB |
Output is correct |
| 9 |
Correct |
17 ms |
3192 KB |
Output is correct |
| 10 |
Correct |
33 ms |
6392 KB |
Output is correct |
| 11 |
Correct |
40 ms |
7928 KB |
Output is correct |
| 12 |
Correct |
89 ms |
16000 KB |
Output is correct |
| 13 |
Correct |
113 ms |
19504 KB |
Output is correct |
| 14 |
Correct |
127 ms |
22800 KB |
Output is correct |
| 15 |
Correct |
154 ms |
24504 KB |
Output is correct |
| 16 |
Correct |
174 ms |
26172 KB |
Output is correct |
| 17 |
Correct |
180 ms |
27964 KB |
Output is correct |
| 18 |
Correct |
149 ms |
29620 KB |
Output is correct |
| 19 |
Correct |
157 ms |
31288 KB |
Output is correct |
| 20 |
Correct |
190 ms |
33012 KB |
Output is correct |
