CSacademy Decreasing Subarrays

#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(0)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back
#define mset(c,v) memset(c , v , sizeof c)
#define loop0(n) for(int i=0; i<n; i++)
#define loop1(n) for(int i=1; i<=n; i++)
#define mpair(x , y) make_pair(x , y)
#define all(x) x.begin(), x.end()
#define pi acos(-1.0)
#define psb push_back

typedef unsigned long long ull;
typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef vector<string>vs;
typedef map<int, int>mpii;
typedef map<string, int>mpsi;
typedef map<char, int>mpci;
typedef map<LL, LL>mpll;

const int mod = 1000007;
const int high = 1e5+5;
const int inf = 1e9;

// you have to just print longest sub-array size index wise.
 /*

 Example:

3 2 1 1 4
for 3: 3 2 1 is the longest sub array, size = 3;
    for 2: 2 1 : size = 2, but you have got size 3 from the before. so 3 is the ans.
    for 1: size = 3.
    again, for 1: now, as the said on the first sample... 3 2 1 1 is not decreasing, which means strictly decreasing
    so, in that case longest size = 1 whatever, 4 right of 1 is greater than 1.
    for 4: size = 1..

    so output: 3 3 3 1 1

 */

int main()
{
    fast;
    int i , N;
    while(cin >> N)
    {
        int x;

        cin >> x;

        int last = x , len = 1;

        bool fl = false;

        for(i=1; i<N; i++)
        {
            cin >> x;

            if(last > x)
            {
                len++;
            }

            else
            {
                for(int j=0; j<len; j++)
                {
                    if(!fl)
                    {
                        cout << len;
                        fl = true;
                    }

                    else cout << " " << len;
                }

                len = 1;
            }

            last = x;
        }

        for(i=0; i<len; i++)
        {
            cout << " " << len;
        }

        cout << "\n";
    }

    return 0;
}

Comments

Popular posts from this blog

SPOJ-CMG - Collecting Mango

LightOJ 1009 - Back to Underworld

LeetCode Palindrome Number