#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int maxn=1e5+7;
const int mod=30013;
const int maxx=1e9+7;
void cmax(pair<int,int>&a,pair<int,int>b)
{
if(a.fi<b.fi)a=b;
else{
if(a.fi==b.fi&&a.fi!=0)a.se=(a.se+b.se)%mod;
}
}
int id(int x,vector<pair<int,int>>tmp)
{
return lower_bound(tmp.begin(),tmp.end(),make_pair(x,-maxx))-tmp.begin()+1;
}
struct BIT
{
private:
int n;
vector<pair<int,int>>t;
public:
BIT(){}
BIT(int n):n(n),t(n+7,make_pair(0,1)){}
void up(int x,pair<int,int> val){
for(;x<=n;x+=(x&(-x)))cmax(t[x],val);
}
pair<int,int>get(int x)
{
if(x<=0)return {0,1};
pair<int,int>res={0,1};
for(;x;x-=(x&(-x)))cmax(res,t[x]);
return res;
}
};
vector<int>a,b,c,d;
int n;
pair<int,int>ans[maxn];
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
a.resize(n+1);b.resize(n+1);
c.resize(n+1);d.resize(n+1);
vector<pair<int,int>>top;
vector<pair<int,int>>bot;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i]>>d[i];
top.push_back({a[i],i});
top.push_back({b[i],i});
bot.push_back({c[i],i});
bot.push_back({d[i],i});
}
sort(begin(top),end(top));
sort(begin(bot),end(bot));
bot.erase(unique(begin(bot),end(bot)),end(bot));
BIT t(2*bot.size()+7);
for(auto[x,i]:top){
if(x==a[i]){
pair<int,int>tmp=t.get(id(c[i],bot)-1);
ans[i]={tmp.fi+1,tmp.se};
}
else if(x==b[i]){
t.up(id(d[i],bot),ans[i]);
}
}
pair<int,int>res={0,0};
for(int i=1;i<=n;i++){
cmax(res,ans[i]);
}
cout<<res.fi<<" "<<res.se;
return 0;
}
Compilation message
trapezoid.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
42 | main()
| ^~~~
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:61:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | for(auto[x,i]:top){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
10 ms |
688 KB |
Output is correct |
| 6 |
Correct |
14 ms |
856 KB |
Output is correct |
| 7 |
Correct |
23 ms |
888 KB |
Output is correct |
| 8 |
Correct |
34 ms |
856 KB |
Output is correct |
| 9 |
Correct |
125 ms |
1492 KB |
Output is correct |
| 10 |
Execution timed out |
605 ms |
2508 KB |
Time limit exceeded |
| 11 |
Execution timed out |
840 ms |
3020 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1060 ms |
5320 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1038 ms |
6160 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1038 ms |
7172 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1042 ms |
7608 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1046 ms |
8112 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1014 ms |
8632 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1046 ms |
9136 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1074 ms |
9500 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1045 ms |
9908 KB |
Time limit exceeded |
