SEDMAX - Editorial

memset(nextgreater,-1,sizeof(nextgreater)); 
memset(previousgreater,-1,sizeof(previousgreater)); 

consider T= 10^5

1 Like

Yes ,but it is given that sum of N will not exceed 10^6 over all test cases

The sum of N over all test cases does not exceed 10^6 is not equivalent to the sum of 100000+5 over all test cases does not exceed 10^6
In short, size of both the arrays is set to 100000+5 globally thus complexity of your code becomes (100000+5 ) \cdot T where T<=10^5.

1 Like

Oh shit , I get it now. I totally didn’t see that and was trying to find any logical from last 2 hrs.
thanks a lot for help XD

1 Like

import itertools

def difmax(l):
diff=abs(l[0]-l[1])
return diff

n=int(input())
for i in range(n):
w=[]
m=int(input())
h=list(map(int,input().split()))
p=list(set(h))

c=itertools.combinations(p,2)
for k in c:
    g=list(k)
    w.append(difmax(g))

print(len(set(w)))

please help me find the mistake

Please explain to me why my code is not even passing subtask1

My Submission

Code
    #include <bits/stdc++.h>
    using namespace std;

typedef long long ll;
typedef ll type;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<char, int> pci;
typedef pair<int, int> pii;

#define mod 1000000007;
#define frz(i, k, n) for (type i = k; i > n; i--)
#define fr(i, k, n) for (type i = k; i < n; i++)
#define _sort(v) sort(v.begin(), v.end())
#define rsort(v) sort(v.rbegin(), v.rend())
#define l_b(v, c) lower_bound(v.begin(), v.end(), c)
#define u_b(v, c) upper_bound(v.begin(), v.end(), c)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define dbg(x) cout << #x << " = " << x << "\n"
const ll inf = 0x3f3f3f3f3f3f3f3fll;

//Print any set
template <class class_name>
void print_set(set<class_name> vec)
{
cout << endl;
for (auto item : vec)
{
    cout << item << " ";
}
cout << endl;
}

void solve()
{
ll n;
cin >> n;
vl arr(n);
set<ll> cost;
fr(i, 0, n) cin >> arr[i];
fr(i, 0, n-1)
{
    ll high1 = max(arr[i], arr[i + 1]);
    ll high2 = min(arr[i], arr[i + 1]);
    cost.insert(high1-high2);
    fr(j, i + 2, n)
    {
        if (arr[j] > high1)
        {
            high1 = arr[j];
            high2 = high1;
        }
        else if (arr[j] > high2)
            high2 = arr[j];
        
        cost.insert(high1 - high2);
    }
}
// print_set(cost);
cout << cost.size() << endl;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
cin >> t;
for (int it = 1; it <= t; it++)
{
    solve();
}
return 0;
}

When you found in your code arr[j]>high1, then you are making both high1 and high2 equal to arr[j]

1 Like

Thank you for helping me.
Such silly mistakes waste a lot of time.

I am getting this verdict, I have spent over 5 hours trying to figure out what’s wrong with my code. I have also compared my code with editorialist’s code and his output on different cases and I cant find anything wrong. Please please help me find out what I am doing wrong.

My code: click here

Please help me out.

How to come with such observation.
I guess to think element wise that
how this element can contribute to the answer.