Poisonous Plants

                            Solution in C :

In C++ :





#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
in dct=0;
map<in,in> mar;
set<in> td;
void proc(in id){
  auto it=mar.find(id);
  auto it2=it;
  ++it2;
  mar.erase(it);
  if(it2!=mar.end() && it2!=mar.begin()){
    it=it2;
    --it;
    if(it2->second>it->second)
      td.insert(it2->first);
    else{
      if(td.count(it2->first))
	td.erase(it2->first);
    }
  }
}
VI otd;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n;
  cin>>n;
  in ta;
  forn(i,n){
    cin>>ta;
    mar[i]=ta;
    if(i>0 && mar[i]>mar[i-1])
      td.insert(i);
  }
  while(!td.empty()){
    dct++;
    otd.clear();
    fors(i,td)
      otd.PB(*i);
    td.clear();
    reverse(all(otd));
    forv(i,otd){
      proc(otd[i]);
    }
  }
  cout<<dct<<endl;
  return 0;
}








In Java :





import java.util.Scanner;


public class Solution {
    private Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Solution().solve();
    }

    private void solve() {
        int n = sc.nextInt();

        int[] p = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = sc.nextInt();
        }

        int min = p[0];
        int maxDays = 0;
        for (int i = 1; i < n; ++i) {
            min = Math.min(min, p[i]);
            if (p[i] > p[i - 1]) {
                int last = p[i];
                int k = i + 1;
                int days = 1;
                while (k < n && min < p[k]) {
                    if (p[k] <= last) {
                        last = p[k];
                        ++days;
                    }
                    ++k;
                }

                maxDays = Math.max(maxDays, days);
            }
        }

        System.out.println(maxDays);
    }
}








In C :




#include<stdio.h>
int main(){
    long int n,i,j,min=0,locmin;
    scanf("%ld",&n);
    long long int *p=(long long int *)malloc(sizeof(long long int)*n);
    for(i=0;i<n;i++)
    scanf("%lld",&p[i]);
    
    i=n-2;
    j=n-1;
    
    while(i>=0){
               if(j<n && p[j]>p[i]){
                      locmin=0;
                              while(j<n && (p[j]>p[i] || p[j]<0)){
  
                              
                              //if(p[j-1]<0)
                              if(p[j]>0)
                              p[j]=locmin-1;
                              
                              if(locmin>p[j])
                              locmin = p[j];
                              //else
                              //p[j] = -1;
                              j++;               
                              }  
               }
               j=i;
               i--;
    }
    for(i=0;i<n;i++){
                     if(p[i]<min)
                     min=p[i];
    }
    printf("%ld ",-min);
    free(p);
    return 0;
}








In Python3 :






class plant:
    def __init__(self, pest):
        self.pest = pest
        self.prevkiller = self.nextkiller = None
    __slots__ = 'pest,next,prevkiller,nextkiller'.split(',')
    
nplants = int(input())
plants = [int(pest) for pest in input().split()]
start = current = plant(plants[0])
curkiller = firstkiller = plant(None)
for pest in plants[1:]:
    current.next = newplant = plant(pest)
    if current.pest < newplant.pest:
            curkiller.nextkiller = current
            current.prevkiller = curkiller
            curkiller = current
    current = newplant
last = current.next = plant(-1)
last.prevkiller = curkiller
curkiller.nextkiller = last
day = 0
while last.prevkiller is not firstkiller:
    day += 1
    curkiller = last.prevkiller
    while curkiller is not firstkiller:
        victim = curkiller.next
        if not(hasattr(victim, "next")):
            print(victim.pest, day)
        curkiller.next = victim.next
        if victim.prevkiller == curkiller:
            curkiller.nextkiller = victim.nextkiller
            victim.nextkiller.prevkiller = curkiller
            victim.prevkiller = victim.nextkiller = None
        curkiller = curkiller.prevkiller

    curkiller = last.prevkiller
    while curkiller is not firstkiller:
        prevkiller = curkiller.prevkiller
        if curkiller.pest >= curkiller.next.pest:
            curkiller.nextkiller.prevkiller = prevkiller
            prevkiller.nextkiller = curkiller.nextkiller
            curkiller.prevkiller = curkiller.nextkiller = None
        curkiller = prevkiller
print(day)