結果
問題 | No.2333 Slime Structure |
ユーザー |
👑 ![]() |
提出日時 | 2023-05-28 15:34:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 290 ms / 3,000 ms |
コード長 | 8,958 bytes |
コンパイル時間 | 1,203 ms |
コンパイル使用メモリ | 91,748 KB |
最終ジャッジ日時 | 2025-02-13 13:35:19 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#line 1 "..\\Main.cpp"#include <iostream>#include <string>#include <vector>#include <algorithm>#include <atcoder/modint>#line 1 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\vec.hpp"#line 3 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\vec.hpp"#include <iterator>#line 5 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\vec.hpp"template<class Elem> struct vec;struct iotai;template<class Iter>struct seq_view{using Ref = typename std::iterator_traits<Iter>::reference;using Elem = typename std::iterator_traits<Iter>::value_type;Iter a, b;Iter begin() const { return a; }Iter end() const { return b; }int size() const { return (int)(b-a); }seq_view(Iter first, Iter last) : a(first), b(last) {}seq_view sort() const { std::sort(a, b); return *this; }Ref& operator[](int x){ return *(a+x); }template<class F, class ret = vec<int>> ret sorti(F f) const {ret x(iotai(0), iotai(size()));x().sort([&](int l, int r){ return f(a[l],a[r]); });return x;}template<class ret = vec<Elem>> ret col() const { return ret(begin(), end()); }template<class F> seq_view sort(F f) const { std::sort(a, b, f); return *this; }Iter uni() const { return std::unique(a, b); }Iter lb(const Elem& x) const { return std::lower_bound(a, b, x); }Iter ub(const Elem& x) const { return std::upper_bound(a, b, x); }template<class F> Iter lb(const Elem& x, F f) const { return std::lower_bound(a, b, x, f); }template<class F> Iter ub(const Elem& x, F f) const { return std::upper_bound(a, b, x, f); }template<class F> Iter when_true_to_false(F f) const {if(a == b) return a;return std::lower_bound(a, b, *a,[&](const Elem& x, const Elem& y){ return f(x); });}seq_view same(Elem x) const { return { lb(x), ub(x) }; }template<class F> auto map(F f) const {vec<typename Iter::value_type> r;for(auto& x : *this) r.emp(f(x));return r;}Iter max() const { return std::max_element(a, b); }Iter min() const { return std::min_element(a, b); }seq_view rev() const { std::reverse(a, b); return *this; }};struct iotai {using i64 = long long;using Me = iotai;using value_type = i64;using iterator_category = std::random_access_iterator_tag;using difference_type = ptrdiff_t;using pointer = i64*;using reference = i64&;i64 x;iotai(i64 y) : x(y) {}i64 operator*() const { return x; }std::size_t operator-(Me a) const { return x - a.x; }Me operator++(){ return { (i64)(++x) }; }Me operator--(){ return { (i64)(--x) }; }Me operator++(int){ return { (i64)(x++) }; }Me operator--(int){ return { (i64)(x--) }; }Me operator+(std::size_t a) const { return { (i64)(x+a) }; }Me operator-(std::size_t a) const { return { (i64)(x-a) }; }static seq_view<iotai> range(i64 l, i64 r){ return { Me{l}, Me{r} }; }};template<class Elem>struct vec {using Base = typename std::vector<Elem>;using Iter = typename Base::iterator;using CIter = typename Base::const_iterator;using View = seq_view<Iter>;using CView = seq_view<CIter>;vec(){}explicit vec(int n, const Elem& value = Elem()) : a(0<n?n:0, value) {}template <class I2> vec(I2 first, I2 last) : a(first, last) {}vec(std::initializer_list<Elem> il) : a(std::move(il)) {}operator Base() const { return a; }Iter begin(){ return a.begin(); }CIter begin() const { return a.begin(); }Iter end(){ return a.end(); }CIter end() const { return a.end(); }int size() const { return a.size(); }vec sortunied(){ vec x = *this; x().sort(); x.a.erase(x().uni(), x.end()); return x; }Iter operator()(int x){ return (x < 0 ? a.end() : a.begin()) + x; }CIter operator()(int x) const { return (x < 0 ? a.end() : a.begin()) + x; }View operator()(int l, int r){ return { (*this)(l), (*this)(r) }; }CView operator()(int l, int r) const { return { (*this)(l), (*this)(r) }; }View operator()(){ return (*this)(0,size()); }CView operator()() const { return (*this)(0,size()); }Elem& operator[](int x){ return *((*this)(x)); }const Elem& operator[](int x) const { return *((*this)(x)); }Base& operator*(){ return a; }const Base& operator*() const { return a; }template<class... Args>vec& emp(Args &&... args){a.emplace_back(std::forward<Args>(args) ...);return *this;}template<class Range>vec& app(Range& x){ for(auto& v : a) emp(v); }Elem pop(){Elem x = std::move(a.back());a.pop_back(); return x;}Base a;};#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\segment-tree.hpp"#line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\segment-tree.hpp"namespace nachia{template<class S,S op(S l, S r)>struct SegmentTree {private:int N;std::vector<S> A;void mergev(int i){if(i < N) A[i] = op(A[i*2], A[i*2+1]);}public:SegmentTree(int n, S e){N = 1; while (N < n) N *= 2;A.assign(N * 2, e);}SegmentTree(const std::vector<S>& a, S e) : SegmentTree(a.size(), e){for(int i=0; i<(int)a.size(); i++) A[i + N] = a[i];for(int i=N-1; i>=1; i--) mergev(i);}void set(int p, S x){p += N; A[p] = x;for(int d=1; (1<<d)<=N; d++) mergev(p>>d);}S get(int p){ return A[N+p]; }S prod(int l, int r) const {l += N; r += N;S ql = A[0], qr = A[0];while(l<r){if(l&1) ql = op(ql, A[l++]);if(r&1) qr = op(A[--r], qr);l /= 2;r /= 2;}return op(ql, qr);}S allProd() const { return A[1]; }// bool cmp(S)template<class E>int minLeft(int r, E cmp, int a = 0, int b = 0, int i = -1){static S x;if(i == -1){ a=0; b=N; i=1; x=A[0]; }if(r <= a) return a;if(b <= r){S nx = op(A[i], x);if(cmp(nx)){ x = nx; return a; }}if(b - a == 1) return b;int q = minLeft(r, cmp, (a+b)/2, b, i*2+1);if(q > (a+b)/2) return q;return minLeft(r, cmp, a, (a+b)/2, i*2);}// bool cmp(S)template<class E>int maxRight(int l, E cmp, int a = 0, int b = 0, int i = -1){static S x;if(i == -1){ a=0; b=N; i=1; x=A[0]; }if(b <= l) return b;if(l <= a){S nx = op(x, A[i]);if(cmp(nx)){ x = nx; return b; }}if(b - a == 1) return a;int q = maxRight(l, cmp, a, (a+b)/2, i*2);if(q < (a+b)/2) return q;return maxRight(l, cmp, (a+b)/2, b, i*2+1);}};} // namespace nachia#line 8 "..\\Main.cpp"using namespace std;using i32 = int;using u32 = unsigned int;using i64 = long long;using u64 = unsigned long long;#define rep(i,n) for(int i=0; i<(int)(n); i++)const i64 INF = 1001001001001001001;using Modint = atcoder::static_modint<998244353>;struct S {i64 ans;i64 l;i64 r;i64 sum;bool e = false;};S op(S l, S r){if(r.e) return l;if(l.e) return r;r.l += l.sum;r.r += l.sum;return { max({ l.ans, r.ans, r.r - l.l }), min(l.l, r.l), max(l.r, r.r), l.sum + r.sum };}int main(){int N, Q; cin >> N;vector<pair<i64, i64>> A(N);rep(i,N) cin >> A[i].first >> A[i].second;cin >> Q;vector<i64> T(Q), X(Q), Y(Q);rep(i,Q) cin >> T[i] >> X[i] >> Y[i];vec<i64> P(N+1);rep(i,N) P[i+1] = P[i] + A[i].second;rep(i,Q){if(T[i] == 1){X[i]--;P.emp(X[i]);P.emp(X[i]+1);}if(T[i] == 2){X[i]--;P.emp(X[i]);P.emp(Y[i]);}}P = P.sortunied();vector<i64> H(P.size()-1); {i64 p = 0;for(auto [a,b] : A){i64 q = p + b;i64 l = P().lb(p) - P(0);i64 r = P().lb(q) - P(0);for(i64 i=l; i<r; i++) H[i] = a;p = q;}}auto seg = nachia::SegmentTree<S, op>(P.size()-1, {INF,-INF,-INF,0,true});rep(i,P.size()-1){S q;i64 w = P[i+1] - P[i];q.ans = max(H[i], H[i] * w);q.l = min((w-1) * H[i], 0ll);q.r = max(w * H[i], H[i]);q.sum = w * H[i];seg.set(i, q);}rep(qi, Q){if(T[qi] == 1){i64 p = P().lb(X[qi]) - P(0);seg.set(p, { Y[qi], 0, Y[qi], Y[qi] });}else{i64 l = P().lb(X[qi]) - P(0);i64 r = P().lb(Y[qi]) - P(0);cout << seg.prod(l, r).ans << '\n';}}return 0;}struct ios_do_not_sync{ios_do_not_sync(){ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_instance;