#include<bits/stdc++.h>
using namespace std;
const long long maxn = 1e5+3;
const long long maxq = 4e5+3;
const long long mod = 30013;
long long i,j,p,q,n,m,k;
pair <long long,long long> dp[maxn];
pair <long long,long long> a[maxn];
struct Trapeze
{
long long a[5];///a b c d
}tr[maxn];
struct Coordinate
{
long long val;
long long type;
long long ind;
};
vector <Coordinate> coordinates;
bool ul[maxq],ur[maxq];
pair <long long,long long> fen[maxq];
void upd(long long p,long long d,long long br)
{
while(p<=maxq)
{
if(d>fen[p].first)
fen[p] = {d,br};
else if(d==fen[p].first)
fen[p].second+=br,fen[p].second%=mod;
p = (p|(p+1));
}
}
pair <long long,long long> rsq(long long p)
{
pair <long long,long long> ans={0,0};
while(p>=0)
{
if(ans.first<fen[p].first)
ans = fen[p];
else if(ans.first==fen[p].first)
ans.second+=fen[p].second,ans.second%=mod;
p = ((p&(p+1))-1);
}
return ans;
}
bool fff(Coordinate a,Coordinate b)
{
return a.val<b.val;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n;
for(i=1;i<=n;i++)
{
cin>>tr[i].a[1]>>tr[i].a[2]>>tr[i].a[3]>>tr[i].a[4];
coordinates.push_back({tr[i].a[1],1,i});
coordinates.push_back({tr[i].a[2],2,i});
coordinates.push_back({tr[i].a[3],3,i});
coordinates.push_back({tr[i].a[4],4,i});
}
sort(coordinates.begin(),coordinates.end(),fff);
for(i=0;i<coordinates.size();i++)
{
auto t = coordinates[i];
tr[t.ind].a[t.type] = i+1;
}
coordinates.push_back({4*n+2,1,n+1});
tr[n+1].a[3]=4*n+2;
upd(0,0,1);
for(i=1;i<=4*n+1;i++)
{
auto t = coordinates[i];
if(t.type==1)
{
dp[t.ind] = rsq(tr[t.ind].a[3]);
dp[t.ind].first++;
}
else if(t.type==2)
{
upd(tr[t.ind].a[4],dp[t.ind].first,dp[t.ind].second);
}
}
pair <long long,long long> ans = rsq(4*n+2);
cout<<ans.first<<" "<<ans.second<<endl;
return 0;
}
Compilation message
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:66:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Coordinate>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(i=0;i<coordinates.size();i++)
| ~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
0 ms |
340 KB |
Partially correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
2 ms |
788 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1104 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1360 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1484 KB |
Output is correct |
| 9 |
Correct |
11 ms |
2376 KB |
Output is correct |
| 10 |
Correct |
22 ms |
4664 KB |
Output is correct |
| 11 |
Correct |
34 ms |
5496 KB |
Output is correct |
| 12 |
Correct |
61 ms |
10116 KB |
Output is correct |
| 13 |
Correct |
71 ms |
12972 KB |
Output is correct |
| 14 |
Correct |
93 ms |
15252 KB |
Output is correct |
| 15 |
Correct |
96 ms |
15644 KB |
Output is correct |
| 16 |
Correct |
109 ms |
17296 KB |
Output is correct |
| 17 |
Correct |
117 ms |
18460 KB |
Output is correct |
| 18 |
Correct |
123 ms |
19204 KB |
Output is correct |
| 19 |
Correct |
114 ms |
19168 KB |
Output is correct |
| 20 |
Correct |
131 ms |
20800 KB |
Output is correct |
