oj.uz

Submission #370289

# Submission time Handle Problem Language Result Execution time Memory
370289 2021-02-23T16:48:49 Z silverfish Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 2000 ms 8820 KB 
#include <bits/stdc++.h>
using namespace std;

/*<DEBUG>*/
#define tem template <typename 
#define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i)
#define _op debug& operator<<
tem C > auto test(C *x) -> decltype(cerr << *x, 0LL);
tem C > char test(...);
tem C > struct itr{C begin, end; };
tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; }
struct debug{
#ifdef _LOCAL
	~debug(){ cerr << endl; }
	tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; }
	tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); }
	tem T, typename U > _op (pair<T, U> i){ 
		return *this << "< " << i.first << " , " << i.second << " >"; }
	tem T> _op (itr<T> i){
		*this <<  "{ ";
		for(auto it = i.begin; it != i.end; it++){
			*this << " , " + (it==i.begin?2:0) << *it;
		}
		return *this << " }";
	}
#else
tem T> _op (const T&) { return *this; }
#endif 
};

string _ARR_(int* arr, int sz){
	string ret = "{ " + to_string(arr[0]); 
	for(int i = 1; i < sz; i++) ret += " , " +  to_string(arr[i]);
	ret += " }"; return ret;
}

#define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]"
/*</DEBUG>*/

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pb push_back
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define TC int __TC__; cin >> __TC__; while(__TC__--)
#define ar array

const ll INF = 1e18 + 7, N = 2e5 + 1;

ll a[N], dp[N][2], tree[N];
int n, q; 

bool cmp(ll a, ll b){
	return a < b;
}


bool sign(ll x){
	return x<0;
}

// 0 : choose
// 1 : not chose

void add(int i, ll v){
	for(; i <= n; i += i&-i) tree[i] += v;
}

ll query(int i){
	if(i <= 0 || i >= n+1) return 0;
	ll ret = 0;
	for(; i >= 1; i -= i&-i) ret += tree[i];
	return ret;
}

ll get_diff(int i){
	return query(i+1) - query(i);
}

ll calc(){
	dp[1][0] = abs(get_diff(1));
	dp[1][1] = 0;

	for(int i = 2; i <= n-1; ++i){

		if(sign(get_diff(i)) != sign(get_diff(i-1))){
			dp[i][0] = abs(get_diff(i)) + dp[i-1][1];
			dp[i][1] = max(dp[i-1][1], dp[i-1][0]);
		}else{
			dp[i][0] = abs(get_diff(i)) + max(dp[i-1][0], dp[i-1][1]);
			dp[i][1] = max(dp[i-1][0], dp[i-1][1]);
		}

	}
	return max(dp[n-1][0], dp[n-1][1]);
}



int main(void)
{
	FAST;
	cin >> n >> q;
	for(int i = 1; i <= n; ++i) cin >> a[i];

	add(1, a[1]);
	for(int i = 2; i <= n; ++i){
		add(i, a[i] - a[i-1]);
	}


	while(q--){
		ll v;
		int l, r; cin >> l >> r >> v;

		add(l, v);
		if(r < n) add(r+1, -v);

		cout << calc() << '\n';
	}
	return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 286 ms 748 KB Output is correct
8 Correct 295 ms 648 KB Output is correct
9 Correct 293 ms 632 KB Output is correct
10 Correct 295 ms 748 KB Output is correct
11 Correct 285 ms 632 KB Output is correct
12 Correct 239 ms 620 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 286 ms 748 KB Output is correct
8 Correct 295 ms 648 KB Output is correct
9 Correct 293 ms 632 KB Output is correct
10 Correct 295 ms 748 KB Output is correct
11 Correct 285 ms 632 KB Output is correct
12 Correct 239 ms 620 KB Output is correct
13 Execution timed out 2071 ms 8820 KB Time limit exceeded
14 Halted 0 ms 0 KB -