SRM647 div1 easy BuildingTowersEasy

考えたこと

• AtCoder Expressを思い出す
• x[i-1] から x[i] までの区間についてどこまで上げられるのかみたいなのを考える
• よくよく考えると前後それぞれから見ていけばいいだけ
• dp1[i] = (i以前の条件を満たす最大の高さ), dp2[i] = (i以後の条件を満たす最大の高さ) とするとi番目で可能な最大の高さはmin(dp1[i], dp2[i])
• O(N)でそれぞれ求める

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class BuildingTowersEasy {
   public:
   int maxHeight(int N, vector <int> x, vector <int> t)
  {
    int n = x.size();
    VI height(N, -1);
    height[0] = 0;
    REP(i, n) {
      height[x[i]-1] = t[i];
      // cerr << x[i]-1 << " " << t[i] << endl;
    }

    VI ret1(N), ret2(N);
    int now = 0;
    REP(i, N) {
      if(height[i] != -1) chmin(now, height[i]);
      // cout << i << " " << now << endl;
      ret1[i] = now++;
    }

    now = INF;
    for(int i=N-1; i>=0; --i) {
      if(height[i] != -1) chmin(now, height[i]);
      ret2[i] = now++;
    }

    int ans = 0;
    REP(i, N) {
      chmax(ans, min(ret1[i], ret2[i]));
    }
    return ans;
  }
};