# Submit Info #2588

Problem Lang User Status Time Memory
Segment Add Get Min cpp Nyaan WA 2568 ms 158.62 MiB

ケース詳細
Name Status Time Memory
example_00 AC 6 ms 0.57 MiB
example_01 AC 7 ms 0.68 MiB
max_random_00 WA 2372 ms 158.59 MiB
max_random_01 WA 2568 ms 158.51 MiB
max_random_02 WA 2433 ms 158.62 MiB
random_00 WA 1643 ms 127.10 MiB
random_01 WA 1810 ms 129.38 MiB
random_02 WA 606 ms 46.74 MiB
small_00 AC 6 ms 0.59 MiB
small_01 WA 8 ms 0.59 MiB

#include <bits/stdc++.h> #define pb push_back #define eb emplace_back #define fi first #define se second #define rep(i,N) for(long long i = 0; i < (long long)(N); i++) #define repr(i,N) for(long long i = (long long)(N) - 1; i >= 0; i--) #define rep1(i,N) for(long long i = 1; i <= (long long)(N) ; i++) #define repr1(i,N) for(long long i = (N) ; (long long)(i) > 0 ; i--) #define each(x,v) for(auto& x : v) #define all(v) (v).begin(),(v).end() #define sz(v) ((int)(v).size()) #define ini(...) int __VA_ARGS__; in(__VA_ARGS__) #define inl(...) long long __VA_ARGS__; in(__VA_ARGS__) #define ins(...) string __VA_ARGS__; in(__VA_ARGS__) using namespace std; void solve(); using ll = long long; template<class T = ll> using V = vector<T>; using vi = V<int>; using vl = V<>; using vvi = V< V<int> >; constexpr int inf = 1001001001; constexpr ll infLL = (1LL << 61) - 1; struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7);} } iosetupnya; template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; } template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; } template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); rep(i,s) os << (i ? " " : "") << v[i]; return os; } template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; } void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);} void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);} template<typename T>void die(T x){out(x); exit(0);} #ifdef NyaanDebug #include "NyaanDebug.h" #define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0) #define trca(v,N) do { cerr << #v << " = "; array_out(v , N);cout << endl;} while(0) #else #define trc(...) #define trca(...) int main(){solve();} #endif using P = pair<ll,ll>; using vp = V<P>; constexpr int MOD = /**/ 1000000007; //*/ 998244353; ////////// template<typename T , T INF> struct DynamicLiChaoTree{ struct Line{ T slope , intercept; Line() : slope(0),intercept(INF){} Line(T slope,T intercept) : slope(slope),intercept(intercept){} inline T get(T x) const{ return slope * x + intercept; } inline bool over(const Line& other , const T &x) const{ return get(x) < other.get(x); } }; // remind セグ木は1-indexedの実装 T xmin, xmax, _size; unordered_map<T, Line> seg; // [l , r]におけるLi Chao Tree DynamicLiChaoTree(T xmin, T xmax) : xmin(xmin), xmax(xmax){ _size = 1; while(_size < xmax - xmin + 1) _size <<= 1; } // 内部用の関数 void update(T a,T b,T left,T right,T seg_idx){ Line line(a , b); while(1){ T mid = (left + right) >> 1; bool l_over = line.over(seg[seg_idx], min(xmax , left + xmin) ); bool r_over = line.over(seg[seg_idx], min(xmax , right-1+ xmin) ); if(l_over == r_over){ if(l_over) swap(seg[seg_idx] , line); return; } bool m_over = line.over(seg[seg_idx], min(xmax , mid + xmin) ); if(m_over) swap(seg[seg_idx], line); if(l_over != m_over) seg_idx = (seg_idx << 1) , right = mid; else seg_idx = (seg_idx<<1) | 1 , left = mid; } } // 内部用の関数 void update(T a, T b, T seg_idx){ T left , right; T upper_bit = 63 - __builtin_clzll(seg_idx); left = (_size >> upper_bit) * (seg_idx - (1 << upper_bit) ); right = left + (_size >> upper_bit); update(a , b , left , right , seg_idx); } /* void update(T a,T b,T left,T right){ T lower_bit = (left | right) & (- (left | right) ); T seg_idx = ( _size + left ) / lower_bit; update(a , b , left , right , seg_idx); } */ // y = ax + bなる直線を追加 void update(T a, T b){ update(a , b , 0 , _size , 1); } // 閉区間x in [left , right]に線分y = ax + bを追加するクエリ void update_line_segment(T a,T b,T left,T right){ left -= xmin - _size, right -= xmin - _size - 1; for( ; left < right; left >>= 1 , right >>= 1){ if(left & 1) update(a , b , left++); if(right& 1) update(a , b , --right); } } // xにおける最小値クエリ T query(T x) { T left = 0 , right = _size , seg_idx = 1 , idx = x - xmin , ret = INF; while(1){ T cur = seg[seg_idx].get(x); // 線分追加クエリがない場合はここのコメントアウトを外して高速化可能(1.5倍程度？) //if(cur == INF) break; ret = min(ret , cur); if(left + 1 >= right) break; T mid = (left + right) >> 1; if(idx < mid) seg_idx = (seg_idx << 1) , right = mid; else seg_idx = (seg_idx << 1) | 1 , left = mid; } return ret; } void merge(DynamicLiChaoTree<T,INF> &other){ if(seg.size() < other.seg.size()) seg.swap(other.seg); for(auto &x : other.seg){ if(x.second.intercept == INF) continue; update(x.second.slope , x.second.intercept , x.first); } } }; void solve(){ ini(N , Q); DynamicLiChaoTree<ll , infLL> lichao(-1001001001 , 1001001001); rep(i , N){ inl(l , r , a , b); lichao.update_line_segment(a , b , l , r - 1); } rep(i , Q){ inl(c); if(c == 0){ ini(l , r , a , b); lichao.update_line_segment(a , b , l , r - 1); } else { inl(x); ll ans = lichao.query(x); if(ans >= infLL) out("INFINITY"); else out(ans); } } }