CS Academy 076 DIV2 D - Pyramids

えーーーーー、どうしてバグに気づかなかった。。。orz

問題へのリンク

問題概要

x 軸上に斜辺を持つような直角二等辺三角形 (三頂点はどれも格子点) が N 個与えられる。N 個の直角二等辺三角形によって被覆される格子点の総数を求めよ。

制約

• 1 <= N <= 10⁵

考えたこと

区間 [a, b) が区間 [p, q) に完全に覆われるとき、区間 [a, b) は除去する前処理を行って得られる区間集合について終端でソートすると

• 始端も終端も単調非減少

という状態にすることができる。で、上記の区間 [a, b) を除去する作業を行うために

• 最初に区間の終端でソート
• 始端の値が最小の index i をとると、i より前の区間は i に包含される
• 次に [i, N) の範囲で始端の値が最小の index i2 をとると、、、を繰り返す

という風にすれば実現できる。後ろからの累積和ならぬ累積 max 的なものを持っておけば実現できる。区間ソートも含めてここまで でできる。

さて、こうなると扱いやすくなって、終端が小さい順に

• 直角二等辺三角形が前回のと重なるなら重なりを引きつつ加算する

という風にしていけばよい (ここで何故か重ならなくても謎の量を引いてしまっていてそのバグになかなか気づかなかった)。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<long long, long long> pll;
int N;
vector<pll> inters;

bool cmp(pll a, pll b) { return a.second < b.second; }

long long area(long long n) {
    if (n < 0) return 0;
    long long m = (n+1)/2;
    if (n & 1) return m*m;
    else return m*(m+1);
}

int main() {
    cin >> N;
    inters.resize(N);
    for (int i = 0; i < N; ++i) {
        long long a, b; cin >> a >> b;
        inters[i].first = b - (a-1);
        inters[i].second = b+1 + (a-1);
    }
    sort(inters.begin(), inters.end(), cmp);
    vector<int> smin(N+1), imin(N+1);
    smin[N] = 1<<30;
    imin[N] = -1;
    for (int i = N-1; i >= 0; --i) {
        if (smin[i+1] < inters[i].first) smin[i] = smin[i+1], imin[i] = imin[i+1];
        else smin[i] = (int)inters[i].first, imin[i] = i;
    }

    long long res = 0;
    int cur = -1;
    for (int i = 0; i < N; ++i) {
        int next = imin[cur+1];
        if (next == -1) break;
        long long tmp = 0;
        if (i == 0) tmp = area(inters[next].second - inters[next].first);
        else tmp = area(inters[next].second - inters[next].first) - area(inters[cur].second - inters[next].first);
        res += tmp;
        cur = next;
    }
    cout << res << endl;
}