oj.uz

답안 #370309

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
370309 2021-02-23T17:25:42 Z silverfish Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 2000 ms 7148 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 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 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 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 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 300 ms 768 KB Output is correct
8 Correct 305 ms 748 KB Output is correct
9 Correct 313 ms 764 KB Output is correct
10 Correct 303 ms 620 KB Output is correct
11 Correct 301 ms 748 KB Output is correct
12 Correct 237 ms 632 KB Output is correct

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 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 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 300 ms 768 KB Output is correct
8 Correct 305 ms 748 KB Output is correct
9 Correct 313 ms 764 KB Output is correct
10 Correct 303 ms 620 KB Output is correct
11 Correct 301 ms 748 KB Output is correct
12 Correct 237 ms 632 KB Output is correct
13 Execution timed out 2097 ms 7148 KB Time limit exceeded
14 Halted 0 ms 0 KB -