Here is my solution for the problem at CodeChef: Practical coding for everyone :-
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, x, y;
cin >> n >> x >> y;
vector<pair<int, int>> event;
int s, e;
for(int i=0; i<n; i++)
{
cin >> s >> e;
event.push_back({s, e});
}
vector<int> v(x);
vector<int> w(y);
for(int i=0; i<x; i++)
cin >> v[i];
sort(v.begin(), v.end());
for(int i=0; i<y; i++)
cin >> w[i];
sort(w.begin(), w.end());
vector<int> time;
for(auto E : event)
{
int l = upper_bound(v.begin(), v.end(), E.first) - v.begin();
int r = lower_bound(w.begin(), w.end(), E.second) - w.begin();
if(l == 0 || l == v.size() || r == w.size())
continue;
else
{
int t1 = v[l-1];
int t2 = w[r];
time.push_back(t2-t1+1);
}
}
int min_time = *min_element(time.begin(), time.end());
cout << min_time << "\n";
return 0;
}
The above code gets AC in all the tasks except for task 4 and 6 where it gives WA and RE respectively. I am unable to figure out the fault in the code, can anyone please help me with this?
Try
1 1 1
10 12
9
13
If you aren’t able to debug it, here are my 2 ways of correcting it.
Way 1
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, x, y;
cin >> n >> x >> y;
vector<pair<int, int>> event;
int s, e;
for(int i=0; i<n; i++)
{
cin >> s >> e;
event.push_back({s, e});
}
vector<int> v(x);
vector<int> w(y);
for(int i=0; i<x; i++)
cin >> v[i];
sort(v.begin(), v.end());
for(int i=0; i<y; i++)
cin >> w[i];
sort(w.begin(), w.end());
vector<int> time;
for(auto E : event)
{
int l = upper_bound(v.begin(), v.end(), E.first) - v.begin();
int r = lower_bound(w.begin(), w.end(), E.second) - w.begin();
if(l == 0 || r == w.size()){
continue;
}
if(l==v.size()){
//The last element may be ok even if it returns a pointer to the end
if(v[l-1]>E.first){
continue;
}
}
int t1 = v[l-1];
int t2 = w[r];
time.push_back(t2-t1+1);
}
int min_time = *min_element(time.begin(), time.end());
cout << min_time << "\n";
return 0;
}
Way 2
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, x, y;
cin >> n >> x >> y;
vector<pair<int, int>> event;
int s, e;
for(int i=0; i<n; i++)
{
cin >> s >> e;
event.push_back({s, e});
}
vector<int> v(x);
vector<int> w(y);
for(int i=0; i<x; i++)
cin >> v[i];
sort(v.begin(), v.end(), greater<int>());
for(int i=0; i<y; i++)
cin >> w[i];
sort(w.begin(), w.end());
vector<int> time;
for(auto E : event)
{
int l = lower_bound(v.begin(), v.end(), E.first,greater<int>()) - v.begin();
int r = lower_bound(w.begin(), w.end(), E.second) - w.begin();
if(r == w.size() || l==v.size()){
continue;
}
int t1 = v[l];
int t2 = w[r];
time.push_back(t2-t1+1);
}
int min_time = *min_element(time.begin(), time.end());
cout << min_time << "\n";
return 0;
}
2 Likes
What is the use of greater() in lower_bound as used in Way 2?
Oh i forgot to comment the second one.
First we sort v
in descending order. Then the lower bound with greater<int>()
returns the largest value less than or equal to E.first.
. I hope you know the default argument is less<int>()
.
2 Likes