結果

問題 No.2974 関数の芽
ユーザー 👑 binap
提出日時 2024-09-22 17:50:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,175 bytes
コンパイル時間 7,535 ms
コンパイル使用メモリ 338,644 KB
実行使用メモリ 28,772 KB
最終ジャッジ日時 2024-09-22 19:30:21
合計ジャッジ時間 13,988 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef long double ld;
typedef pair<int, int> P;
template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;}
template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;}
template <int m> istream& operator>>(istream& is, static_modint<m>& a) {long long x; is >> x; a = x; return is;}
template <int m> istream& operator>>(istream& is, dynamic_modint<m>& a) {long long x; is >> x; a = x; return is;}
template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}
template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return 
    os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); 
    return os;}
template<typename T> ostream& operator<<(ostream& os, const set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename S, auto op, auto e> ostream& operator<<(ostream& os, const atcoder::segtree<S, op, e>& seg){int n = seg.max_right(0, [](S){return 
    true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}
template<typename S, auto op, auto e, typename F, auto mapping, auto composition, auto id> ostream& operator<<(ostream& os, const atcoder
    ::lazy_segtree<S, op, e, F, mapping, composition, id>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n 
    - 1 ? "\n" : " "); return os;}
template<typename T> void chmin(T& a, T b){a = min(a, b);}
template<typename T> void chmax(T& a, T b){a = max(a, b);}
struct Query{
    long long k, l, m, n, x;
};
struct Rational{
    long long up, down;
    Rational(long long _up, long long _down){
        assert(_down != 0);
        int c = 1;
        if(_up < 0){c *= -1; _up *= -1;}
        if(_down < 0){c *= -1; _down *= -1;}
        long long g = gcd(_up, _down);
        up = c * _up / g;
        down = _down / g;
    }
    bool operator<(const Rational& right) const{
        return up * right.down < right.up * down;
    }
    bool operator==(const Rational& right) const{
        return (up * right.down - right.up * down) == 0;
    }
};
// Coodinate Compression
// https://youtu.be/fR3W5IcBGLQ?t=8550
template<typename T=int>
struct CC {
  bool initialized;
  vector<T> xs;
  CC(): initialized(false) {}
  void add(T x) { xs.push_back(x);}
  void init() {
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    initialized = true;
  }
  int operator()(T x) {
    if (!initialized) init();
    return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
  }
  T operator[](int i) {
    if (!initialized) init();
    return xs[i];
  }
  int size() {
    if (!initialized) init();
    return xs.size();
  }
};
using S = pair<long long, long long>;
S op(S a, S b){
    return make_pair(a.first + b.first, a.second + b.second);
}
S e(){
    return make_pair(0LL, 0LL);
}
using F = pair<long long, long long>;
S mapping(F f, S x){
    return make_pair(f.first + x.first, f.second + x.second);
}
F composition(F f, F g){
    return make_pair(f.first + g.first, f.second + g.second);
}
F id(){
    return make_pair(0LL, 0LL);
}
const long long INF = 1001001001;
int main(){
    int q;
    cin >> q;
    vector<Query> querys;
    CC<Rational> cc;
    cc.add(Rational{-INF, 1});
    cc.add(Rational{INF, 1});
    rep(i, q){
        long long k, l, m, n, x;
        cin >> k >> l >> m >> n >> x;
        querys.emplace_back(k, l, m, n, x);
        if(k != 0) cc.add(Rational{-l, k});
        if(m != 0) cc.add(Rational{-n, m});
        cc.add(Rational{x, 1});
    }
    int sz = cc.size();
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(sz);
    
    /*
    for(auto rational : cc.xs){
        cout << rational.up << ' ' << rational.down << "\n";
    }
    */
    
    // apply F(x) += c * max(kx + l, 0)
    auto add = [&](long long k, long long l, long long c){
        if(k > 0){
            seg.apply(cc(Rational(-l, k)), sz, make_pair(c * k, c * l));
        }
        if(k == 0){
            seg.apply(0, sz, make_pair(0, c * l));
        }
        if(k < 0){
            seg.apply(0, cc(Rational(-l, k)), make_pair(c * k, c * l));
        }
    };
    auto judge = [&](long long x){
        int idx = cc(Rational{x, 1});
        auto line_left = seg.get(idx - 1);
        auto line_right = seg.get(idx);
//      cout << line_left << "\n";
//      cout << line_right << "\n";
        if(line_left != e()) return false;
        if(line_right != e()) return false;
        return true;
    };
    rep(i, q){
        auto [k, l, m, n, x] = querys[i];
        add(k, l, 1);
        add(m, n, -1);
        if(judge(x)) cout << "Yes\n";
        else cout << "No\n";
        /*
        rep(idx, sz) cout << seg.get(idx) << ' ';
        cout << "\n";
        */
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0