#include<bits/stdc++.h>
#define int long long
using namespace std;
int md=30013;
int sec=0;
struct trap{
int a,b,c,d;
int id;
trap(int w=0,int x=0,int y=0,int z=0,int i=0){
a=w,b=x,c=y,d=z;
id=i;
}
bool operator<(const trap &x){
if(sec==0)return a<x.a;
return b<x.b;
}
};
struct segtree{
struct node{
int val,cnt;
node(int v=0,int cn=0){
val=v,cnt=cn;
}
friend node operator+(node a,node b){
node c;
c.val=max(a.val,b.val);
c.cnt=(a.val==b.val?a.cnt+b.cnt:(a.val>b.val?a.cnt:b.cnt))%md;
return c;
}
};
node info[1600005];
void upd(int st,int en,int i,int pos,int val,int cnt){
if(st>pos||en<pos)return;
if(st==en)return void(info[i]=node(val,cnt));
int m=(st+en)/2;
upd(st,m,i*2,pos,val,cnt);
upd(m+1,en,i*2+1,pos,val,cnt);
info[i]=info[i*2]+info[i*2+1];
}
node fans(int st,int en,int i,int l,int r){
if(st>r||en<l)return node();
if(st>=l&&en<=r)return info[i];
int m=(st+en)/2;
return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r);
}
}tr;
queue<pair<pair<int,int>,pair<int,int> >>q;
vector<trap>vb;
vector<trap>v;
vector<int>ord;
int num[100005][2];
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
for(int i=0;i<n;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
v.push_back(trap(a,b,c,d,i));
vb.push_back(trap(a,b,c,d,i));
ord.push_back(a);
ord.push_back(b);
ord.push_back(c);
ord.push_back(d);
}
sort(ord.begin(),ord.end());
sort(v.begin(),v.end());
sec=1;
sort(vb.begin(),vb.end());
int cur=0;
for(int i=0;i<v.size();i++){
while(cur<n&&vb[cur].b<v[i].a){
int pos=lower_bound(ord.begin(),ord.end(),vb[cur].d)-ord.begin()+1;
tr.upd(1,4*n,1,pos,num[vb[cur].id][0],num[vb[cur].id][1]);
cur++;
}
int pos=lower_bound(ord.begin(),ord.end(),v[i].c-1)-ord.begin()+1;
auto temp=tr.fans(1,4*n,1,1,pos);
num[v[i].id][0]=temp.val+1;
num[v[i].id][1]=temp.val==0?1:temp.cnt;
//cerr<<v[i].id<<" "<<num[v[i].id][0]<<" "<<num[v[i].id][1]<<"\n";
}
while(cur<n){
int pos=lower_bound(ord.begin(),ord.end(),vb[cur].d)-ord.begin()+1;
tr.upd(1,4*n,1,pos,num[vb[cur].id][0],num[vb[cur].id][1]);
cur++;
}
cout<<tr.info[1].val<<" "<<tr.info[1].cnt;
}
Compilation message
trapezoid.cpp: In function 'int32_t main()':
trapezoid.cpp:71:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<trap>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
26716 KB |
Output is correct |
| 2 |
Correct |
5 ms |
26716 KB |
Output is correct |
| 3 |
Correct |
5 ms |
26972 KB |
Output is correct |
| 4 |
Correct |
6 ms |
26968 KB |
Output is correct |
| 5 |
Correct |
6 ms |
27228 KB |
Output is correct |
| 6 |
Correct |
7 ms |
27480 KB |
Output is correct |
| 7 |
Correct |
8 ms |
27480 KB |
Output is correct |
| 8 |
Correct |
11 ms |
27860 KB |
Output is correct |
| 9 |
Correct |
16 ms |
28576 KB |
Output is correct |
| 10 |
Correct |
24 ms |
30148 KB |
Output is correct |
| 11 |
Correct |
34 ms |
30524 KB |
Output is correct |
| 12 |
Correct |
67 ms |
34096 KB |
Output is correct |
| 13 |
Correct |
90 ms |
35348 KB |
Output is correct |
| 14 |
Correct |
107 ms |
42312 KB |
Output is correct |
| 15 |
Correct |
110 ms |
41524 KB |
Output is correct |
| 16 |
Correct |
116 ms |
42520 KB |
Output is correct |
| 17 |
Correct |
130 ms |
40496 KB |
Output is correct |
| 18 |
Correct |
117 ms |
42272 KB |
Output is correct |
| 19 |
Correct |
124 ms |
41760 KB |
Output is correct |
| 20 |
Correct |
139 ms |
41496 KB |
Output is correct |
