oj.uz

Submission #379631

# Submission time Handle Problem Language Result Execution time Memory
379631 2021-03-18T23:13:33 Z limabeans Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 973 ms 49260 KB 
#include <bits/stdc++.h>
using namespace std;
 
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
 
 
 
 
 
using ll = long long;
 
 
const int maxn = 2e5+10;
 
 
 
int n,q;
ll a[maxn];
 
 
//00
//01
//10
//11
 
ll sgn(ll x) {
    if (x==0) return 0;
    if (x>0) return 1;
    if (x<0) return -1;
    
    assert(false);
    return 1;
}
 
struct node {
    ll lval, rval;
    ll dp[2][2];
    node() {
	lval = rval = 0;
	memset(dp, 0, sizeof(dp));
    }

    node(ll x) {
	lval = rval = x;
	memset(dp, 0, sizeof(dp));
	dp[1][1] = abs(x);
    }
};
 
void setmax(ll &x, ll y) {
    x = max(x, y);
}
 
node merge(node x, node y) {
    node res;


    // [i,k0] [k1,j]
    for (int i=0; i<2; i++) {
	for (int j=0; j<2; j++) {
	    for (int k0=0; k0<2; k0++) {
		for (int k1=0; k1<2; k1++) {
		    bool mergable = true;
		    if (k0==1 && k1==1) {
			if (sgn(x.rval)*sgn(y.lval) == -1) {
			    mergable = false;
			}
		    }
		    
		    if (mergable) {
			setmax(res.dp[i][j], x.dp[i][k0]+y.dp[k1][j]);
		    }
		}
	    }
	}
    }

    res.lval = x.lval;
    res.rval = y.rval;

    return res;
}
 
node t[4*maxn];
 
void upd(int v, int tl, int tr, int i, ll dx) {
    if (tl==tr) {
	ll prev = t[v].lval;
	t[v] = node(prev+dx);
    } else {
	int tm=(tl+tr)/2;
	if (i<=tm) {
	    upd(2*v,tl,tm,i,dx);
	} else {
	    upd(2*v+1,tm+1,tr,i,dx);
	}
	t[v]=merge(t[2*v],t[2*v+1]);
    }
}
 
 
void build(int v, int tl, int tr) {
    if (tl==tr) {
	if (tl>1) {
	    t[v]=node(a[tl]-a[tl-1]);
	} else {
	    t[v]=node();
	}
    } else {
	int tm = (tl+tr)/2;
	build(2*v,tl,tm);
	build(2*v+1,tm+1,tr);
	t[v]=merge(t[2*v],t[2*v+1]);
    }
}
 
 
void update(int l, int r, ll dx) {
    if (l>1) {
	upd(1,1,n,l,dx);
    }
    if (r<n) {
	upd(1,1,n,r+1,-dx);
    }
 
}
 
ll solve() {
    ll res = 0;
    for (int i=0; i<2; i++) {
	for (int j=0; j<2; j++) {
	    res = max(res, t[1].dp[i][j]);
	}
    }
    return res;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
 
    cin>>n>>q;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }
 
    build(1,1,n);
    //watch(solve());
 
    while (q--) {
	int l,r,dx;
	cin>>l>>r>>dx;
	update(l,r,dx);
	cout<<solve()<<"\n";
    }
    
    
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37868 KB Output is correct
2 Correct 25 ms 37868 KB Output is correct
3 Correct 21 ms 37868 KB Output is correct
4 Correct 22 ms 37996 KB Output is correct
5 Correct 22 ms 37868 KB Output is correct
6 Correct 21 ms 37868 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37868 KB Output is correct
2 Correct 25 ms 37868 KB Output is correct
3 Correct 21 ms 37868 KB Output is correct
4 Correct 22 ms 37996 KB Output is correct
5 Correct 22 ms 37868 KB Output is correct
6 Correct 21 ms 37868 KB Output is correct
7 Correct 29 ms 38144 KB Output is correct
8 Correct 29 ms 38124 KB Output is correct
9 Correct 30 ms 38020 KB Output is correct
10 Correct 29 ms 38124 KB Output is correct
11 Correct 30 ms 38124 KB Output is correct
12 Correct 28 ms 38124 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37868 KB Output is correct
2 Correct 25 ms 37868 KB Output is correct
3 Correct 21 ms 37868 KB Output is correct
4 Correct 22 ms 37996 KB Output is correct
5 Correct 22 ms 37868 KB Output is correct
6 Correct 21 ms 37868 KB Output is correct
7 Correct 29 ms 38144 KB Output is correct
8 Correct 29 ms 38124 KB Output is correct
9 Correct 30 ms 38020 KB Output is correct
10 Correct 29 ms 38124 KB Output is correct
11 Correct 30 ms 38124 KB Output is correct
12 Correct 28 ms 38124 KB Output is correct
13 Correct 954 ms 48812 KB Output is correct
14 Correct 963 ms 48816 KB Output is correct
15 Correct 924 ms 48748 KB Output is correct
16 Correct 933 ms 48620 KB Output is correct
17 Correct 973 ms 48748 KB Output is correct
18 Correct 833 ms 49260 KB Output is correct