oj.uz

Submission #907783

# Submission time Handle Problem Language Result Execution time Memory
907783 2024-01-16T04:37:35 Z a_l_i_r_e_z_a Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
 5 ms 348 KB 
// 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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -