oj.uz

Submission #956972

# Submission time Handle Problem Language Result Execution time Memory
956972 2024-04-02T18:16:48 Z hocln Sjeckanje (COCI21_sjeckanje) C++17
55 / 110
 2000 ms 7600 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(), v.end()
#define logg(x) (31 - __builtin_clz(x))
#define llogg(x) (63 - __builtin_clzll(x))
#define mini(v) min_element(v.begin(), v.end())
#define maxi(v) max_element(v.begin(), v.end())
#define TIME cerr << double(clock() - st) / (double)CLOCKS_PER_SEC
#define sq(a) ((a)*(a))
#ifdef hocln
#include "deb.h"
#else
#define imie(...) ""
#define debug() cerr
#endif
#define int long long
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;
typedef tuple<ll, ll, ll> triple;
typedef tuple<ll, ll, ll, ll, ll> five;
typedef unsigned long long ull;
const long long INF = 4e18;
const int inf = 2e9;
const int MN = 3e5 + 15;
const int MX = 2e6 + 15;
const long long MOD = 1e9 + 7;
//long long MOD = 998244353;
const long double PI = 3.141592653589793238462643383279502884197;
template<typename T, typename T2> bool chmax(T& a, const T2& b) { return a < b ? a = b, 1 : 0; }
template<typename T, typename T2> bool chmin(T& a, const T2& b) { return a > b ? a = b, 1 : 0; }
template<typename T> using vector2 = vector<vector<T>>;
const int dx[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
const int dy[] = { 1, -1, 0, 0 , 1, -1, 1, -1};
std::random_device rd;
std::mt19937 gen(rd());
ll random(ll low, ll high) { uniform_int_distribution<> dist(low, high); return dist(gen); }
template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first;
    return is >> p.second;
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto &i: v) os << i << ' ';
    return os;
}
int tc = 0;
// I hate cp
inline void solve_test() {
	int n, q;
	cin >> n >> q;
	vector<ll>v(n);
	for(auto& i : v) cin >> i;
	while(q--) {
		ll l, r, x;
		cin >> l >> r >> x;
		if(n == 1) {
			cout << "0\n";
			continue;
		}
		for(int i = l - 1;i < r;i++) v[i] += x;
		vector<ll>dp(n+1);
		ll d[n];
		for(int i = 0;i < n-1;i++) d[i] = v[i+1]-v[i];
		dp[0]=abs(d[0]);
		for(int i = 1;i < n-1;i++) {
			if((d[i] > 0) == (d[i-1] > 0)) {
				chmax(dp[i],dp[i-1] + abs(d[i]));
			}
			if(i > 1) chmax(dp[i],dp[i-2] + abs(d[i]));
			else chmax(dp[i],abs(d[i]));
			chmax(dp[i],dp[i-1]);
			//debug()<<imie(i)imie(dp[i])imie(d[i]);
		}
		if(n == 1) cout << "0\n";
		else cout << dp[n-2] << '\n';
	}
}
 
int32_t main()
{
    //srand(chrono::steady_clock::now().time_since_epoch().count());
    //freopen("teamwork.in", "r", stdin);
    //freopen("teamwork.out", "w", stdout);
    //cout << "Case #" << tc << ": " << ans << '\n';
    //cout << fixed << setprecision(7);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int tt = 1;
    //cin >> tt;
    while(tt--) {
		++tc;
        solve_test();
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 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 32 ms 636 KB Output is correct
8 Correct 34 ms 632 KB Output is correct
9 Correct 33 ms 600 KB Output is correct
10 Correct 33 ms 600 KB Output is correct
11 Correct 32 ms 604 KB Output is correct
12 Correct 26 ms 604 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 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 32 ms 636 KB Output is correct
8 Correct 34 ms 632 KB Output is correct
9 Correct 33 ms 600 KB Output is correct
10 Correct 33 ms 600 KB Output is correct
11 Correct 32 ms 604 KB Output is correct
12 Correct 26 ms 604 KB Output is correct
13 Execution timed out 2066 ms 7600 KB Time limit exceeded
14 Halted 0 ms 0 KB -