結果

問題 No.180 美しいWhitespace (2)
ユーザー outline
提出日時 2021-03-07 19:48:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,588 bytes
コンパイル時間 2,154 ms
コンパイル使用メモリ 136,024 KB
最終ジャッジ日時 2025-01-19 12:49:19
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <array>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
using namespace std;

using ll = long long;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template<typename T>
struct LichaoTree{
    struct Line{
        T a, b;
        Line(T a, T b) : a(a), b(b) {}
        inline T get(T x) const {return a * x + b;}
        inline bool over(const Line &b, const T &x) const{
            return get(x) < b.get(x);
        }
    };

    // 座標集合
    vector<T> xs;
    
    // 直線集合
    // 区間の半分以上で最小値を取る直線の情報を格納
    // これを見れば最小値が分かるというわけではなく、リーフノードまで見る必要がある。
    vector<Line> seg;
    int sz;

    LichaoTree(const vector<T> &x, T INF) : xs(x){
        sz = 1;
        while(sz < xs.size())   sz <<= 1;
        while(xs.size() < sz)   xs.push_back(xs.back() + 1);
        seg.assign(2 * sz - 1, Line(0, INF));
    }

    void update(Line &x, int k, int l, int r){
        int mid = (l + r) >> 1;
        // bool
        auto latte = x.over(seg[k], xs[l]), malta = x.over(seg[k], xs[mid]);
        // malta = true ならば、今見ている区間で最小値を取り得る直線を交換
        if(malta)   swap(seg[k], x);
        
        if(l + 1 >= r)  return;
        // 左半分を更新
        else if(latte != malta) update(x, 2 * k + 1, l, mid);
        // 右半分を更新
        else    update(x, 2 * k + 2, mid, r);
    }

    // 直線 ax+b=0 を直線集合に入れる
    void update(T a, T b){
        Line l(a, b);
        update(l, 0, 0, sz);
    }

    // xs に入っている k 番目の座標に対するクエリ (座標そのものの値ではないことに注意)
    // 区間 [0, sz) から区間 [k, k+1) まで最小値候補を見ていって、その中の最小値を返す
    T query(int k){
        const T x = xs[k];
        k += sz - 1;
        T ret = seg[k].get(x);
        while(k > 0){
            k = (k - 1) >> 1;
            ret = min(ret, seg[k].get(x));
        }
        return ret;
    }

    void debug(){
        for(int i = 0; i < sz; ++i){
            cerr << seg[i].a << " " << seg[i].b << "\n";
        }
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, a, b;
    cin >> n;
    vector<ll> x(1000001);
    for(int i = 0; i <= 1000000; ++i)   x[i] = i;
    LichaoTree<ll> min_lct(x, 3e+18), max_lct(x, 3e+18);
    for(int i = 0; i < n; ++i){
        cin >> a >> b;
        min_lct.update(b, a);
        max_lct.update(-b, -a);
    }
    int ans = INF;
    ll min_val = 7e+18;
    for(int i = 1; i <= 1000000; ++i){
        ll val = -max_lct.query(i) - min_lct.query(i);
        if(chmin(min_val, val)) ans = i;
        else if(val == min_val) chmin(ans, i);
    }
    cout << ans << endl;

    return 0;
}
0