oj.uz

Submission #490865

# Submission time Handle Problem Language Result Execution time Memory
490865 2021-11-29T14:44:29 Z inksamurai Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 119000 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) (ll)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define crep(i,x,n) for(ll i=x;i<n;i++)
#define drep(i,n) for(ll i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _31av4qi 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<ll,ll>;
using vi=vector<ll>;

const ll inf=1e12;

struct node{
	vec(vec(ll)) val;
	ll _back;
	void init(ll __back,vec(vec(ll)) _val){
		_back=__back;
		val=_val;
	}
	node e(){
		node _e;
		_e.init(-inf,{
			{0,-inf},
			{-inf,0}
		});
		return _e;
	}
};
bool isvalid(node l){
	return l._back!=-inf;
}

node op(node l,node r){
	node now;
	now.init(r._back,now.e().val);
	rep(tl,2)rep(tr,2){
		ll merged,additional=0;
		if(isvalid(l)){
			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);
		additional=0;
		if(isvalid(l)){
			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(){
	node _e;
	return _e.e();
}

int main(){
_31av4qi;
	ll n;
	cin>>n;
	ll q;
	cin>>q;
	vec(ll) a(n);
	rep(i,n){
		cin>>a[i];
	}
	vec(ll) _d;
	rep(i,n-1) _d.pb(a[i+1]-a[i]);
	atcoder::segtree<node,op,e> seg(n-1);
	rep(i,n-1){
		node now;
		now.init(_d[i],now.e().val);
		seg.set(i,now);
	}
	auto f_all=[&](ll l,ll 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){
		ll l,r,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],now.e().val);
			seg.set(l-1,now);
		}
		if(r!=n-1){
			now.init(_d[r],now.e().val);
			seg.set(r,now);
		}
		ll ans=f_all(0,n-1);
		cout<<ans<<"\n";
	}
//	
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 332 KB Output is correct
2 Correct 8 ms 428 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 8 ms 332 KB Output is correct
5 Correct 7 ms 332 KB Output is correct
6 Correct 7 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 332 KB Output is correct
2 Correct 8 ms 428 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 8 ms 332 KB Output is correct
5 Correct 7 ms 332 KB Output is correct
6 Correct 7 ms 332 KB Output is correct
7 Correct 165 ms 2152 KB Output is correct
8 Correct 183 ms 2124 KB Output is correct
9 Correct 165 ms 2224 KB Output is correct
10 Correct 170 ms 2228 KB Output is correct
11 Correct 158 ms 2224 KB Output is correct
12 Correct 178 ms 2216 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 332 KB Output is correct
2 Correct 8 ms 428 KB Output is correct
3 Correct 8 ms 332 KB Output is correct
4 Correct 8 ms 332 KB Output is correct
5 Correct 7 ms 332 KB Output is correct
6 Correct 7 ms 332 KB Output is correct
7 Correct 165 ms 2152 KB Output is correct
8 Correct 183 ms 2124 KB Output is correct
9 Correct 165 ms 2224 KB Output is correct
10 Correct 170 ms 2228 KB Output is correct
11 Correct 158 ms 2224 KB Output is correct
12 Correct 178 ms 2216 KB Output is correct
13 Execution timed out 2078 ms 119000 KB Time limit exceeded
14 Halted 0 ms 0 KB -