結果

問題 No.1008 Bench Craftsman
ユーザー firiexpfiriexp
提出日時 2020-03-06 22:55:15
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,160 ms / 2,000 ms
コード長 2,737 bytes
コンパイル時間 1,026 ms
コンパイル使用メモリ 100,684 KB
実行使用メモリ 8,544 KB
最終ジャッジ日時 2023-08-09 21:22:43
合計ジャッジ時間 18,416 ms
ジャッジサーバーID
(参考情報)
judge14 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,384 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1,160 ms
8,476 KB
testcase_06 AC 114 ms
7,524 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 134 ms
4,376 KB
testcase_10 AC 919 ms
8,492 KB
testcase_11 AC 913 ms
8,292 KB
testcase_12 AC 889 ms
8,296 KB
testcase_13 AC 812 ms
8,416 KB
testcase_14 AC 813 ms
8,364 KB
testcase_15 AC 359 ms
8,476 KB
testcase_16 AC 601 ms
8,544 KB
testcase_17 AC 337 ms
8,496 KB
testcase_18 AC 487 ms
8,456 KB
testcase_19 AC 584 ms
8,380 KB
testcase_20 AC 313 ms
5,688 KB
testcase_21 AC 385 ms
5,460 KB
testcase_22 AC 692 ms
5,024 KB
testcase_23 AC 851 ms
6,044 KB
testcase_24 AC 953 ms
6,076 KB
testcase_25 AC 221 ms
7,504 KB
testcase_26 AC 164 ms
5,504 KB
testcase_27 AC 579 ms
4,728 KB
testcase_28 AC 582 ms
7,788 KB
testcase_29 AC 994 ms
8,188 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <limits>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template <class M>
struct DualSegmentTree{
    using T = typename M::T;
    int sz, height{};
    vector<T> lazy;
    explicit DualSegmentTree(int n) {
        sz = 1; while(sz < n) sz <<= 1, height++;
        lazy.assign(2*sz, M::e());
    }

    void eval(int k){
        if(lazy[k] == M::e()) return;
        lazy[(k<<1)|0] = M::f(lazy[(k<<1)|0], lazy[k]);
        lazy[(k<<1)|1] = M::f(lazy[(k<<1)|1], lazy[k]);
        lazy[k] = M::e();
    }
    void thrust(int k){ for (int i = height; i; --i) eval(k>>i); }
    void update(int a, int b, const T &x){
        thrust(a += sz); thrust(b += sz-1);
        for (int l = a, r = b+1;l < r; l >>=1, r >>= 1) {
            if(l&1) lazy[l] = M::f(lazy[l], x), l++;
            if(r&1) --r, lazy[r] = M::f(lazy[r], x);
        }
    }

    T operator[](int k){
        thrust(k += sz);
        return lazy[k];
    }
};

struct Monoid{
    using T = ll;
    static T f(T a, T b) { return a+b; }
    static T e() { return 0; }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    for (auto &&i : v) scanf("%d", &i);
    int ok = 100001, ng = 0;
    DualSegmentTree<Monoid> seg1(n), seg2(n); // seg1 : 傾き, seg2: 定数項
    vector<int> xs(m), ws(m);
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &xs[i], &ws[i]);
        xs[i]--;
    }
    if(accumulate(ws.begin(),ws.end(), 0LL) < *min_element(v.begin(),v.end())) {
        puts("0");
        return 0;
    }
    while(ok-ng > 1){
        int mid = (ok+ng)/2;
        fill(seg1.lazy.begin(),seg1.lazy.end(), 0);
        fill(seg2.lazy.begin(),seg2.lazy.end(), 0);
        for (int i = 0; i < m; ++i) {
            if(xs[i] != 0 && ws[i]/mid != 0) {
                ll l = max(0, xs[i]-ws[i]/mid), r = xs[i];
                seg1.update(l, r, mid);
                seg2.update(l, r, ws[i]-mid*r);
            }
            ll l = xs[i], r = min(n, xs[i]+ws[i]/mid+1);
            seg1.update(l, r, -mid);
            seg2.update(l, r, ws[i]+mid*l);
        }
        int good = 1;
        for (int j = 0; j < n; ++j) {
            if(seg1[j] * j + seg2[j] >= v[j]){
                good = 0;
                break;
            }
        }
        if(good) ok = mid;
        else ng = mid;
    }
    if(ok == 100001){
        puts("-1");
    }else {
        cout << ok << "\n";
    }
    return 0;
}
0