Submit Info #2584

Problem Lang User Status Time Memory
Segment Add Get Min cpp14 Nyaan WA 299 ms 2.43 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.63 MiB
example_01 AC 7 ms 0.63 MiB
max_random_00 WA 299 ms 2.43 MiB
max_random_01 WA 234 ms 2.38 MiB
max_random_02 WA 279 ms 2.43 MiB
random_00 WA 199 ms 2.00 MiB
random_01 WA 191 ms 1.96 MiB
random_02 WA 106 ms 1.66 MiB
small_00 WA 4 ms 0.63 MiB
small_01 WA 7 ms 0.64 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){ int 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; int 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(-inf , inf); rep(i , N){ ini(l , r , a , b); lichao.update_line_segment(a , b , l , r - 1); } rep(i , Q){ ini(c); if(c == 0){ ini(l , r , a , b); lichao.update_line_segment(a , b , l , r - 1); } else { ini(x); ll ans = lichao.query(x); if(ans >= inf) out("INFINITY"); else out(ans); } } }