oj.uz

Submission #1069931

# Submission time Handle Problem Language Result Execution time Memory
1069931 2024-08-22T10:10:38 Z n1k Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 691 ms 44540 KB 
#include <bits/stdc++.h>

#if defined(LOCAL)
#include "debug.cpp"
#else
#define debug(x...) 0
#endif // LOCAL

using namespace std;

using ll = long long;

#define all(a) (a).begin(), (a).end()

vector<ll> a;

struct Data{
	array<array<ll, 2>, 2> mat={};
	ll lo=0, hi=0;
	Data operator+(Data o){
		array<array<ll, 2>, 2> ret={};
		for(int i=0; i<2; i++){
			for(int j=0; j<2; j++){
				for(int x=0; x<2; x++){
					for(int y=0; y<2; y++){
						// ret[i][j], mat[i][x], o.mat[y][j]
						if(x!=1 or y!=1 or signbit(hi) == signbit(o.lo)){
							ret[i][j] = max(ret[i][j], mat[i][x] + o.mat[y][j]);
						}
					}
				}
			}
		}
		return Data{ret, lo, o.hi};
	}
};

struct V{
    int lb=0, rb=0;
	Data val{};
    V *l=nullptr, *r=nullptr;
    V(){};
    V(int lb_, int rb_){lb=lb_, rb=rb_;};
    void ext(){
        if(lb!=rb and not l){
            int mb=(lb+rb)/2;
            l=new V(lb, mb);
            r=new V(mb+1, rb);
        }
    }
    void upd(int id, ll x){
        if(lb==rb and lb==id){
			val = Data{array{array<ll, 2>{0, 0}, array<ll, 2>{0, abs(x)}}, x, x};
        }
        ext();
        if(l){
            if(id<=l->rb){
                l->upd(id, x);
            }else{
                r->upd(id, x);
            }
            val = l->val+ r->val;
        }
    }
    Data qry(int lo, int hi){
        if(lo<=lb and rb<=hi){
            return val;
        }
        if(hi<lb or rb<lo) return Data{};
        ext();
        return l->qry(lo, hi) + r->qry(lo, hi);
    }
};

void solve(){
	int n, q; cin >> n >> q;
	a.assign(n, 0);
	V seg(0, n-2);
	for(int i=0; i<n; i++) cin >> a[i];
	vector<ll> d;
	for(int i=0; i+1<n; i++){
		d.push_back(a[i+1] - a[i]);
		seg.upd(i, d.back());
	}
	a = d;
	while(q--){
		ll l, r, add;
		cin>>l>>r>>add;
		l--, r--;
		if(l){
			d[l-1] += add;
			seg.upd(l-1, d[l-1]);
		}
		if(r<d.size()){
			d[r]-=add;
			seg.upd(r, d[r]);
		}
		auto mat = seg.qry(0, n-1).mat;
		ll ans = 0;
		for(int i=0; i<2; i++){
			for(int j=0; j<2; j++){
				ans = max(ans, mat[i][j]);
			}
		}
		cout<<ans<<endl;
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t=1; //cin >> t;
	while(t--) solve();
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:94:7: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   if(r<d.size()){
      |      ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 7 ms 1080 KB Output is correct
8 Correct 7 ms 860 KB Output is correct
9 Correct 7 ms 892 KB Output is correct
10 Correct 8 ms 860 KB Output is correct
11 Correct 7 ms 860 KB Output is correct
12 Correct 7 ms 1108 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 7 ms 1080 KB Output is correct
8 Correct 7 ms 860 KB Output is correct
9 Correct 7 ms 892 KB Output is correct
10 Correct 8 ms 860 KB Output is correct
11 Correct 7 ms 860 KB Output is correct
12 Correct 7 ms 1108 KB Output is correct
13 Correct 691 ms 42940 KB Output is correct
14 Correct 667 ms 43852 KB Output is correct
15 Correct 687 ms 43848 KB Output is correct
16 Correct 670 ms 43716 KB Output is correct
17 Correct 671 ms 43716 KB Output is correct
18 Correct 654 ms 44540 KB Output is correct