Submission #907783

#	Time	Username	Problem	Language	Result	Execution time	Memory
907783		a_l_i_r_e_z_a	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	5 ms	348 KiB

Main

// In the name of God

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((ll)(x).size())

const ll maxn = 2e5 + 5;
const ll inf = 1e16 + 7;
int n, q;
ll a[maxn];
bool mark[maxn];

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> a[i];
    while(q--){
        ll l, r, x; cin >> l >> r >> x;
        for(int i = l - 1; i < r; i++) a[i] += x;
        set<pll> st;
        fill(mark, mark + n, 0);
        for(int i = 1; i < n; i++) st.insert(mp(abs(a[i] - a[i - 1]), i));
        ll ans = 0;
        while(st.size()){
            ll i = (*st.rbegin()).S, x = (*st.rbegin()).F;
            st.erase((*st.rbegin()));
            if(!mark[i] && !mark[i - 1]){
                mark[i] = mark[i - 1] = 1;
                ans += x;
            }
            else{
                if(mark[i - 1] && (a[i] >= a[i - 1]) != (a[i - 1] >= a[i - 2])) continue;
                if(mark[i] && (a[i] >= a[i - 1]) != (a[i + 1] >= a[i])) continue;
                ans += x;
                mark[i] = mark[i - 1] = 1;
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55