#include <bits/stdc++.h>
using namespace std;
long long n;
vector<tuple<long long,long long,long long,long long> > v;
bool visited[100000];
pair<long long,long long> dp[100000];
/// zima,nacini
pair<long long,long long> f(long long poz)
{
//cout <<"ulava u "<<poz<<endl;
if (poz==v.size()) return {0,0};
if (visited[poz]==true) return dp[poz];
long long zima=0,nacini=1;
pair<long long,long long> p={zima,nacini};
for (int i=0;i<n;i++)
{
if (get<1>(v[poz])<get<0>(v[i]) && get<3>(v[poz])<get<2>(v[i]))
{
//cout<<"poz = "<<poz<<" && i = "<<i<<" "<< get<1>(v[poz])<<" < "<<get<0>(v[i])<<" && "<<get<3>(v[poz])<<" < "<<get<2>(v[i])<<endl;
p=f(i);
if (p.first==zima) nacini+=p.second;
else if(p.first>zima)
{
zima=p.first;
nacini=p.second;
}
}
}
zima++;
p={zima,nacini};
visited[poz]=true;
dp[poz]=p;
return p;
}
int main()
{
cin>>n;
for (long long i=0;i<n;i++)
{
long long A,B,C,D;
cin>>A>>B>>C>>D;
v.push_back({A,B,C,D});
}
//sort(v.begin(),v.end());
pair<long long,long long> p={0,0};
for (long long i=0;i<n;i++)
if (visited[i]==false)
{
pair<long long,long long> q=f(i);
//cout<< "i="<<i<<" zima="<<q.first<<endl<<" najde="<<q.second<<endl;
if (p.first==q.first) p.second+=q.second;
if (q.first>p.first) p=q;
}
//for (int i=1;i<n;i++) if (dp[i].second==p.first) p.second+=dp[i].second;
cout<<p.first<<" "<<p.second<<endl;
return 0;
}
///////
Compilation message
trapezoid.cpp: In function 'std::pair<long long int, long long int> f(long long int)':
trapezoid.cpp:13:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | if (poz==v.size()) return {0,0};
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
340 KB |
Expected int32, but "10313130667392" found |
| 4 |
Incorrect |
4 ms |
340 KB |
Expected int32, but "-8550276992825950208" found |
| 5 |
Partially correct |
17 ms |
468 KB |
Partially correct |
| 6 |
Incorrect |
28 ms |
468 KB |
Expected int32, but "-8629080777422869056" found |
| 7 |
Incorrect |
52 ms |
612 KB |
Expected int32, but "-3319866744691032064" found |
| 8 |
Partially correct |
56 ms |
684 KB |
Partially correct |
| 9 |
Incorrect |
282 ms |
916 KB |
Expected int32, but "2248786528710863832" found |
| 10 |
Execution timed out |
1063 ms |
1404 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1036 ms |
1632 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1075 ms |
2440 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1081 ms |
2632 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1081 ms |
4496 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1081 ms |
4536 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1039 ms |
4532 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1075 ms |
4408 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1077 ms |
4492 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1047 ms |
4528 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1076 ms |
4480 KB |
Time limit exceeded |
