WA and RE in two tasks of Wormholes (ZCO12002)

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?

@everule1 Please help.

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

Thank you :slightly_smiling_face: