IOI 2004 - Empodia

Official Editorial

Let $v[0],v[1],\dots ,v[n-1]$ denote the input sequence. An interval $[i\dots j]$ is framed if all three of the following conditions hold:

• $v[i]-i=v[j]-j$
• $v[i]=\min (v[i\dots j])$
• $v[j]=\max (v[i\dots j])$

Our approach will be to iterate over all $j=[0,n)$ and check whether $j$ contributes a new empodio with right endpoint $j$.

• Maintain a stack $mn$ consisting of all indices $i$ satisfying the second condition.
• When we increment $j$, repeatedly pop the top element $i$ of $mn$ while $v[i]>v[j]$. Then add $j$ to $mn$.
• To check whether $j$ is part of an empodio, find the maximum $i\in mn$ such that $v[i]-i=v[j]-j$. If $i$ is to the right of the rightmost left endpoint of any empodio found so far and $v[j]=\max (v[i\dots j])$, then we have found a new empodio.

To check whether $v[j]=\max (v[i\dots j])$, we can maintain a separate stack $mx$ that stores all indices $i$ such that $v[i]=\max (v[i\dots j])$.

Note: The test data on Yandex has sequences of length greater than $1100000$ $\dots$

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;