oj.uz

답안 #580002

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580002 2022-06-20T12:50:58 Z HeartBreakKid Sjeckanje (COCI21_sjeckanje) C++17
0 / 110
 7 ms 12628 KB 
#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

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

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 12628 KB Output isn't correct
2 Halted 0 ms 0 KB -