#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
int x1[200000],y1[200000],x2[200000],y2[200000];
vector<int> pytaj[200000];
int wynik[200000];
int ile[200000];
map<int,int> mapka;
vector<pair<int,int> > Q;
vector<int> zero;
int pot=1;
int maxxx[2000000];
int ilee[2000000];
int mod=30013;
pair<int,int> combine(int x1,int x2,int y1,int y2)
{
if(x1!=x2)
{
if(x1>x2)
return {x1,y1};
else return {x2,y2};
}
else return {x1,y1+y2};
}
void ustaw(int x,int maxx,int ile)
{
x+=pot;
maxxx[x]=maxx;
ilee[x]=ile;
x/=2;
while(x>0)
{
pair<int,int> para=combine(maxxx[x*2],maxxx[x*2+1],ilee[x*2],ilee[x*2+1]);
maxxx[x]=para.first;
ilee[x]=para.second;
ilee[x]%=mod;
x/=2;
}
}
pair<int,int> zap(int x,int y)
{
x+=pot;
y+=pot;
pair<int,int> wynik;
if(x!=y)
wynik=combine(maxxx[x],maxxx[y],ilee[x],ilee[y]);
else wynik={maxxx[x],ilee[x]};
while(x/2!=y/2)
{
if(x%2==0)
wynik=combine(wynik.first,maxxx[x+1],wynik.second,ilee[x+1]);
if(y%2==1)
wynik=combine(wynik.first,maxxx[y-1],wynik.second,ilee[y-1]);
x/=2;
y/=2;
wynik.second%=mod;
}
wynik.second%=mod;
if(wynik.first==0)
return {0,1};
return wynik;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
for(int i=1;i<=n;i++)
{
mapka[x1[i]]=1;
mapka[y1[i]]=1;
mapka[x2[i]]=1;
mapka[y2[i]]=1;
}
int mam=1;
for(auto it=mapka.begin();it!=mapka.end();it++)
mapka[it->first]=mam++;
while(pot<=mam)
pot*=2;
pot--;
for(int i=1;i<=n;i++)
Q.push_back({y1[i],i});
sort(Q.begin(),Q.end());
for(int i=0;i<Q.size();i++)
{
int pocz=0,kon=i,sre,ostd=-1;
while(pocz<kon)
{
sre=(pocz+kon)/2;
if(y1[Q[sre].second]<x1[Q[i].second])
{
ostd=sre;
pocz=sre+1;
}
else kon=sre;
}
if(ostd>=0)
pytaj[ostd].push_back(i);
else zero.push_back(i);
}
for(int i=0;i<zero.size();i++)
{
int kto=zero[i];
wynik[kto]=1;
ile[kto]=1;
}
for(int i=0;i<Q.size();i++)
{
int kto=Q[i].second;
ustaw(mapka[y2[kto]],wynik[i],ile[i]);
for(int j=0;j<pytaj[i].size();j++)
{
int pytam=pytaj[i][j];
pair<int,int> para=zap(1,mapka[x2[Q[pytam].second]]);
wynik[pytam]=para.first+1;
ile[pytam]=para.second;
ile[pytam]%=mod;
}
}
int maxx=1;
mam=0;
for(int i=0;i<n;i++)
{
if(wynik[i]>maxx)
{
mam=ile[i];
maxx=wynik[i];
}
else if(wynik[i]==maxx)
mam+=ile[i];
}
mam%=mod;
cout<<maxx<<" "<<mam;
return 0;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(int i=0;i<Q.size();i++)
| ~^~~~~~~~~
trapezoid.cpp:108:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int i=0;i<zero.size();i++)
| ~^~~~~~~~~~~~
trapezoid.cpp:114:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i=0;i<Q.size();i++)
| ~^~~~~~~~~
trapezoid.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int j=0;j<pytaj[i].size();j++)
| ~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5128 KB |
Output is correct |
| 5 |
Correct |
6 ms |
5588 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5956 KB |
Output is correct |
| 7 |
Correct |
8 ms |
5720 KB |
Output is correct |
| 8 |
Correct |
16 ms |
6076 KB |
Output is correct |
| 9 |
Correct |
29 ms |
7500 KB |
Output is correct |
| 10 |
Correct |
30 ms |
8464 KB |
Output is correct |
| 11 |
Correct |
53 ms |
11716 KB |
Output is correct |
| 12 |
Correct |
136 ms |
18136 KB |
Output is correct |
| 13 |
Correct |
189 ms |
21168 KB |
Output is correct |
| 14 |
Correct |
204 ms |
24908 KB |
Output is correct |
| 15 |
Correct |
231 ms |
22596 KB |
Output is correct |
| 16 |
Correct |
287 ms |
24172 KB |
Output is correct |
| 17 |
Correct |
264 ms |
27812 KB |
Output is correct |
| 18 |
Correct |
151 ms |
20260 KB |
Output is correct |
| 19 |
Correct |
311 ms |
28636 KB |
Output is correct |
| 20 |
Correct |
287 ms |
29604 KB |
Output is correct |
