SRM513 Div1 Easy - YetAnotherIncredibleMachine

問題

　枚の板について長さと設置できる上下限位置が与えられる。また個のボールが各座標に落とされる。板に一つもボールが落ちないような板の配置方法が何通りあるか求めよ。

解法

　ボールが落ちる位置について累積和を取って、各板が設置可能な範囲を二分探索で求める。

反省

　問題の把握にいくらか時間がかかったのと、端の関係とか二分探索の含める含めない、範囲指定などでかなり混乱した。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

class  YetAnotherIncredibleMachine {
public:
    int countWays(vector<int> platformMount, vector<int> platformLength, vector<int> balls) {
        constexpr int MAX = 2e5;
        vector<int> num(2 * MAX + 2, 0);
       
        int* p = &num[MAX + 1];
        for (int b : balls) {
            p[b]++;
        }
        for (int i = -MAX; i < MAX; i++) {
            p[i + 1] += p[i];
        }

        constexpr ll MOD = 1e9 + 9;
        ll ans = 1;
        for (int i = 0; i < platformMount.size(); i++) {
            ll curr_pattern = 0;

            //可能な左端についてループする
            for (int l = platformMount[i] - platformLength[i]; l <= platformMount[i]; ) {
                if (p[l] == p[l - 1] + 1) {
                    l++;
                    continue;
                }
                int n = p[l];
                int r = upper_bound(&p[l], &p[platformMount[i] + platformLength[i] + 1], n) - &p[0];
                curr_pattern += max(r - l - platformLength[i], 0);
                curr_pattern %= MOD;
                l = r;
            }

            ans *= curr_pattern;
            ans %= MOD;
        }

        return ans;
    }
};