oj.uz

답안 #490876

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
490876 2021-11-29T15:07:33 Z inksamurai Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 580 ms 34916 KB 
#include <bits/stdc++.h>
// cut here
#ifdef _MSC_VER
#include <intrin.h>
#endif
 
namespace atcoder {
 
namespace internal {
 
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}
 
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}
 
}  // namespace internal
 
}  // namespace atcoder
 
 
namespace atcoder {
 
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
 
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
 
    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }
 
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;
 
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
 
    S all_prod() { return d[1]; }
 
    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
 
    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
 
  private:
    int _n, size, log;
    std::vector<S> d;
 
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
 
}  // namespace atcoder
// cut here 
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3cSpNGp ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;

const ll inf=1e12;

struct node{
	ll val[2][2];
	ll back;
	void init(ll _back){
		back=_back;
		val[0][0]=val[1][1]=0;
		val[0][1]=val[1][0]=-inf;
	}
};
node _e;

node op(node l,node r){
	node now;
	now.init(r.back);
	rep(tl,2)rep(tr,2){
		ll merged=0,additional=0;
		
		additional=max(0ll,l.back);
		merged=l.val[tl][0]+r.val[0][tr]+additional; // both positive
		now.val[tl][tr]=max(now.val[tl][tr],merged);
		
		if(l.back!=-inf){
			additional=max(0ll,-l.back);
		}
		merged=l.val[tl][1]+r.val[1][tr]+additional; // both negative
		now.val[tl][tr]=max(now.val[tl][tr],merged);
		
		merged=l.val[tl][0]+r.val[1][tr];
		now.val[tl][tr]=max(now.val[tl][tr],merged);
		
		merged=l.val[tl][1]+r.val[0][tr];
		now.val[tl][tr]=max(now.val[tl][tr],merged);
	}
	return now;
}

node e(){
	return _e;
}
int main(){
_3cSpNGp;
	_e.init(0);
	int n;
	cin>>n;
	int q;
	cin>>q;
	vi a(n);
	rep(i,n){
		cin>>a[i];
	}
	atcoder::segtree<node,op,e> seg(n-1);
	vec(ll) d;
	rep(i,n-1){
		node now;
		d.pb((ll)a[i+1]-a[i]);
		now.init(d.back());
		seg.set(i,now);
	}
	auto f_all=[&](int l,int r)->ll{
		node now=seg.prod(l,r);
		ll ans=-inf;
		rep(t,2)rep(t1,2){
			ans=max(ans,now.val[t][t1]);
		}
		return ans;
	};
	rep(_,q){
		int l,r;
		ll x;
		cin>>l>>r>>x;
		l--,r--;
		if(l) d[l-1]+=x;
		if(r!=n-1) d[r]-=x;
		node now;
		if(l){
			now.init(d[l-1]);
			seg.set(l-1,now);
		}
		if(r!=n-1){
			now.init(d[r]);
			seg.set(r,now);
		}
		ll ans=f_all(0,n-1);
		cout<<ans<<"\n";
	}
//	
	return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 5 ms 812 KB Output is correct
10 Correct 8 ms 776 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 5 ms 716 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 5 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 5 ms 812 KB Output is correct
10 Correct 8 ms 776 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 5 ms 716 KB Output is correct
13 Correct 580 ms 32116 KB Output is correct
14 Correct 532 ms 34344 KB Output is correct
15 Correct 517 ms 34352 KB Output is correct
16 Correct 534 ms 34200 KB Output is correct
17 Correct 540 ms 34168 KB Output is correct
18 Correct 528 ms 34916 KB Output is correct