제출 #199807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
199807		mohamedsobhi777	Pismo (COCI18_pismo)	C++17	0 / 70	39 ms	11132 KiB

pismo

#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