IOI 2004 - Empodia

Author: Benjamin Qi


Official Editorial

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

  • v[i]i=v[j]jv[i]-i=v[j]-j
  • v[i]=min(v[ij])v[i]=\min(v[i\ldots j])
  • v[j]=max(v[ij])v[j]=\max(v[i\ldots j])

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

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

To check whether v[j]=max(v[ij])v[j]=\max(v[i\ldots j]), we can maintain a separate stack mxmx that stores all indices ii such that v[i]=max(v[ij])v[i]=\max(v[i\ldots j]).

Note: The test data on Yandex has sequences of length greater than 11000001100000 \ldots

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!
using pi = pair<int, int>;
using pl = pair<ll, ll>;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!