oj.uz

Submission #199807

# Submission time Handle Problem Language Result Execution time Memory
199807 2020-02-03T13:16:40 Z mohamedsobhi777 Pismo (COCI18_pismo) C++17
0 / 70
 39 ms 11132 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+5 , mod = 1e9 +7 ;

int n ;
string s ;
int a[N] , lg[N];
int l[N] , r[N];
int tab[N][25];

int mn(int l , int r)
{
    int ret ;
    int j = lg[r - l + 1];
    ret = min(tab[l][j], tab[r - (1 << j) + 1][j]);
    return ret ;
}
int main()
{
    lg[1] = 0;
    for (int i = 2; i < N; i++)
    lg[i] = lg[i/2] + 1;

    ios_base::sync_with_stdio(0);
    cin.tie();
    cin>>n;
    vector<int> v = { 0 };
    stack<int> s ;
    s.push(0);
    a[0] = 1e9 +1;
    for(int i = 1;i<=n;i++)
    {
        int t ;
        cin>>t;
        a[i] = t;
        while(s.size() && a[s.top()]< t )
        {
            r[s.top()] = i;
            s.pop();
        }
        l[i] = s.top();
        s.push(i);
    }
    int jj = n+1;
    while(s.size())
    {
        r[s.top()] = jj;
        jj= s.top();
        s.pop();
    }


    for(int i= 1;i<=n;i++)
        tab[i][0] = a[i];

   for (int j = 1; j < 20; j++)
   {
        for (int i = 1; i + (1 << j) <= n+1; i++)
        {
            tab[i][j] = min(tab[i][j-1], tab[i + (1 << (j - 1))][j - 1]);
        }
   }

    int ans = 1e9 ;
    for(int i= 1;i<=n;i++)
    {
        if(r[i] - l[i]==2)
            continue;
        ans = min(ans , mn(l[i]+1 , r[i] -1) );
    }
    cout<<(ans==1e9?0:ans);
    return 0;
}

Subtask #1
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1144 KB Output isn't correct
2 Incorrect 5 ms 1144 KB Output isn't correct
3 Incorrect 6 ms 1400 KB Output isn't correct
4 Incorrect 6 ms 1400 KB Output isn't correct
5 Incorrect 38 ms 11000 KB Output isn't correct
6 Incorrect 39 ms 11132 KB Output isn't correct
7 Incorrect 37 ms 11000 KB Output isn't correct