#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 30013;
struct event
{
int tip;///1 - latura stanga
///2 - latura dreapta
int pozs,pozj;
int index;
};
bool cmp(event x, event y)
{
return x.pozs < y.pozs;
}
struct node
{
int mxm;
int cntm;
};
node combine(node x, node y)
{
node aux;
aux.mxm = max(x.mxm,y.mxm);
aux.cntm=0;
if(x.mxm == aux.mxm)
aux.cntm += x.cntm;
if(y.mxm == aux.mxm)
aux.cntm += y.cntm;
aux.cntm %= MOD;
return aux;
}
int n;
int a[100001];
int b[100001];
int c[100001];
int d[100001];
vector<event> events;
map<int,int> mp;
map<int,int> nor;
int cntn=0;
int rez[100001];
int cntrez[100001];
void normalizare_c_d()
{
for(int i=0;i<n;i++)
{
mp[c[i]]++;
mp[d[i]]++;
}
int val;
for(auto it:mp)
{
val=it.first;
cntn++;
nor[val]=cntn;
}
for(int i=0;i<n;i++)
{
c[i]=nor[c[i]];
d[i]=nor[d[i]];
}
}
node aint[810000];
void upd(int nod, int st, int dr, int poz, node newval)
{
if(st==dr)
{
aint[nod]=newval;
return;
}
int mij=(st+dr)/2;
if(poz<=mij)
upd(nod*2,st,mij,poz,newval);
else
upd(nod*2+1,mij+1,dr,poz,newval);
aint[nod]=combine(aint[nod*2],aint[nod*2+1]);
}
node qry(int nod, int st, int dr, int le, int ri)
{
if(le>ri)
return {0,0};
if(le==st && dr==ri)
return aint[nod];
int mij=(st+dr)/2;
return combine(qry(nod*2,st,mij,le,min(mij,ri)),
qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i]>>b[i]>>c[i]>>d[i];
normalizare_c_d();
for(int i=0;i<n;i++)
{
events.push_back({1,a[i],c[i],i});
events.push_back({2,b[i],d[i],i});
}
sort(events.begin(),events.end(),cmp);
for(auto e:events)
{
if(e.tip==1)
{
///calc rez[e.index]
///rez[e.index] = qry max 1..e.pozj-1
node x = qry(1,1,cntn,1,e.pozj-1);
rez[e.index] = x.mxm + 1;
cntrez[e.index] = max(1LL, x.cntm);
}
else
{
///upd aint on position e.pozj with value rez[e.index]
upd(1,1,cntn,e.pozj,{rez[e.index],cntrez[e.index]});
}
}
int mxmr=0,cntr=0;
for(int i=0;i<n;i++)
{
if(rez[i]>mxmr)
{
mxmr=rez[i];
cntr=cntrez[i];
}
else if(rez[i]==mxmr)
cntr+=cntrez[i],cntr%=MOD;
}
cout<<mxmr<<" "<<cntr%MOD<<"\n";
return 0;
}
/**
a b
c d
trapezul i poate fi selectat in acelasi timp cu trapezul j daca:
d[j] < c[i]
b[j] < a[i]
avem 2 tipuri de eventuri:
1 - latura stanga
2 - latura dreapta
le sortam dupa pozitia capatului de sus
astfel, reducem a 2-a conditie (b[j] < a[i]), stiind ca ea va fi tot timpul adevarata
ne facem un aint pentru cealalta conditie
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
596 KB |
Output is correct |
| 4 |
Correct |
2 ms |
852 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1236 KB |
Output is correct |
| 6 |
Correct |
8 ms |
1744 KB |
Output is correct |
| 7 |
Correct |
8 ms |
2128 KB |
Output is correct |
| 8 |
Correct |
10 ms |
2764 KB |
Output is correct |
| 9 |
Correct |
24 ms |
5072 KB |
Output is correct |
| 10 |
Correct |
41 ms |
9680 KB |
Output is correct |
| 11 |
Correct |
55 ms |
11236 KB |
Output is correct |
| 12 |
Correct |
128 ms |
22480 KB |
Output is correct |
| 13 |
Correct |
150 ms |
26128 KB |
Output is correct |
| 14 |
Correct |
169 ms |
33472 KB |
Output is correct |
| 15 |
Correct |
210 ms |
35652 KB |
Output is correct |
| 16 |
Correct |
258 ms |
37336 KB |
Output is correct |
| 17 |
Correct |
216 ms |
39212 KB |
Output is correct |
| 18 |
Correct |
204 ms |
40716 KB |
Output is correct |
| 19 |
Correct |
224 ms |
41124 KB |
Output is correct |
| 20 |
Correct |
252 ms |
44044 KB |
Output is correct |
