SEDMAX - Editorial


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):
return diff

for i in range(n):

for k in c:


please help me find the mistake

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

My Submission

    #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]);
    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()
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
ll t;
cin >> t;
for (int it = 1; it <= t; it++)
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.