Submission #580002

#	Time	Username	Problem	Language	Result	Execution time	Memory
580002		HeartBreakKid	Sjeckanje (COCI21_sjeckanje)	C++17	0 / 110	7 ms	12628 KiB

Main

#include<bits/stdc++.h>

#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pk pop_back
#define yes cout << "YES\n"
#define no cout << "NO\n"

using namespace std;
//#pragma GCC optimize("Ofast")

//#pragma GCC optimize ("unroll-loops")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

const ll N = 1 << 18;
struct item
{
    ll ans;
    ll x, y;
    item()
    {
        x = 0, y = 0;
        ans = 0;
    }
};
item t[2 * N + 5];
ll a[N];
ll b[N];

ll n, m, k, mod = 1e9 + 7;

void upd(ll i, ll l, ll r)
{
    ll x = b[t[i * 2 + 1].x];
    ll y = b[t[i * 2].y];
    if((r + l) / 2 == l)
        y = 0;
    if(x * y < 0)
        x = max(0LL, abs(x) - abs(y));
    t[i].ans = ((l + r) / 2 != l ? t[i * 2].ans : 0) + ((l + r) / 2 + 1 != r ? t[i * 2 + 1].ans : 0) + abs(x);
    t[i].x = t[i * 2].x;
    t[i].y = t[i * 2 + 1].y;
}

void build(ll i = 1, ll l = 1, ll r = n)
{
    if(l == r)
    {
        t[i].ans = abs(b[l]);
        t[i].x = t[i].y = l;
        return;
    }
    ll mid = (l + r) >> 1;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
    upd(i, l, r);
}
void change(ll l, ll r, ll x, ll l1 = 1, ll r1 = n, ll v = 1)
{
    if(l1 > r || r1 < l)
        return;
    if(l <= l1 && r1 <= r)
    {
        if(l != 1)
        t[v].ans = abs(x);
        return;
    }
    ll mid = (l1 + r1) / 2;
    change(l, r, x, l1, mid, v * 2), change(l, r, x, mid + 1, r1, v * 2 + 1);
    upd(v, l1, r1);
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    cin >> n >> m;
    for(ll i = 1; i <= n; ++i)
        cin >> a[i];
    for(ll i = 2; i <= n; ++i)
        b[i] = a[i] - a[i - 1];
    build();
    for(ll i = 1, l, r, x; i <= m; ++i)
        cin >> l >> r >> x, b[r + 1] -= x, b[l] += x, change(r + 1, r + 1, b[r + 1]), change(l, l, b[l]), cout << t[1].ans << "\n";
}

Compilation message (stderr)

Main.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main()
      | ^~~~

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