Facebook Hacker Cup 2016 Round 2 Snakes and Ladders

,

ケース数$T \le 50$、はしごの数$N \le 200000$、制限時間$360$秒なので$O(n^2)$は怪しい。 しかし、ねぼけて$O(n^2)$で挑んだら通ってしまった。

Tシャツ貰えました。

Snakes and Ladders

問題

はしごが$n$個ある。$i$番目のはしごは位置$x_i$にあって高さは$h_i$である。複数のはしごが同じ位置にあることはない。 以下のような条件を満たすはしごの組$a,b$全てについて、費用が$|b - a|^2$かかる。

  • 高さが同じ。$h_a = h_b$。
  • 間にそれらより真に高いはしごがない。$\forall c. ( x_a \lt x_c \lt x_b \to h_c \le \min \{ h_a, h_b \} )$。

はしごの位置が与えられるので、費用を答えよ。

解法

stackを使って愚直にやれば$O(n^2)$はできる。

想定解法は$O(n)$のようだ。 $(x_a - x_b)^2 = x_a^2 - 2x_ax_b + x_b^2$であるので、 総和に関しても$\Sigma_i (x_i - x_b)^2 = \Sigma_i x_i^2 - (\Sigma_i x_i) \dot 2x_b + x_b^2$である。 $\Sigma_i x_i^2$と$\Sigma_i x_i$を持ちながら同じことをすればよい。

実装

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
struct ladder_t { ll x, h; };
bool operator < (ladder_t a, ladder_t b) { return a.x < b.x; }
const ll mod = 1e9+7;
void solve() {
    int n; cin >> n;
    vector<ladder_t> ls(n);
    repeat (i,n) cin >> ls[i].x >> ls[i].h;
    sort(ls.begin(), ls.end());
    ll ans = 0;
    vector<ladder_t> stk;
    for (auto l : ls) {
        while (not stk.empty() and stk.back().h < l.h) stk.pop_back();
        for (auto it = stk.rbegin(); it != stk.rend() and it->h == l.h; ++ it) {
            ll dx = l.x - it->x;
            ans = (ans +  dx*dx % mod) % mod;
        }
        stk.push_back(l);
    }
    cout << ans << endl;
}
int main() {
    int testcases; cin >> testcases;
    repeat (testcase, testcases) {
        cout << "Case #" << testcase+1 << ": ";
        solve();
    }
    return 0;
}