#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 |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
308 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
316 KB |
Expected int32, but "10313130667392" found |
| 4 |
Incorrect |
4 ms |
400 KB |
Expected int32, but "-8550276992825950208" found |
| 5 |
Partially correct |
13 ms |
500 KB |
Partially correct |
| 6 |
Incorrect |
36 ms |
596 KB |
Expected int32, but "-8629080777422869056" found |
| 7 |
Incorrect |
49 ms |
656 KB |
Expected int32, but "-3319866744691032064" found |
| 8 |
Partially correct |
60 ms |
764 KB |
Partially correct |
| 9 |
Incorrect |
270 ms |
1104 KB |
Expected int32, but "2248786528710863832" found |
| 10 |
Execution timed out |
1087 ms |
1996 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1081 ms |
2228 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1080 ms |
3604 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1081 ms |
4104 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1077 ms |
6508 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1073 ms |
6432 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1063 ms |
6452 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1076 ms |
6568 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1061 ms |
6328 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1081 ms |
6428 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1073 ms |
6420 KB |
Time limit exceeded |
