oj.uz

답안 #367568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367568 2021-02-17T16:59:42 Z MrRobot_28 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 538 ms 23020 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 100;
int tree[4 * N][2][2];
int d[N];
void build(int v, int l, int r)
{
    if(l == r)
    {
        tree[v][0][0] = 0;
        tree[v][1][1] = abs(d[l]);
        return;
    }
    int m = (r + l) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m + 1, r);
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            tree[v][i][j] = 0;
            for(int t = 0; t < 2; t++)
            {
                int t1 = t ^ (d[m] * d[m + 1] < 0);
                tree[v][i][j] = max(tree[v][i][j], tree[v * 2][i][t] + tree[v * 2 + 1][t1][j]);
            }
        }
    }
}
void update(int v, int l, int r, int ind)
{
    if(l == r)
    {
        tree[v][0][0] = 0;
        tree[v][1][1] = abs(d[l]);
        return;
    }
    int m = (r + l) / 2;
    if(ind <= m)
    {
        update(v * 2, l, m, ind);
    }
    if(ind > m)
    {
        update(v * 2 + 1, m + 1, r, ind);
    }
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            tree[v][i][j] = 0;
            for(int t = 0; t < 2; t++)
            {
                int t1 = t ^ (d[m] * d[m + 1] < 0);
                tree[v][i][j] = max(tree[v][i][j], tree[v * 2][i][t] + tree[v * 2 + 1][t1][j]);
            }
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector <int> a(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for(int i = 0; i < n - 1; i++)
    {
        d[i] = a[i + 1] - a[i];
    }
    build(1, 0, n - 1);
    while(q--)
    {
        int l, r, x;
        cin >> l >> r >> x ;
        l--;
        r--;
        if(l != 0)
        {
            d[l - 1] += x;
            update(1, 0, n - 1, l - 1);
        }
        if(r != n - 1)
        {
            d[r] -= x;
            update(1, 0, n - 1, r);
        }
        int ans = 0;
        for(int i = 0; i < 2; i++)
        {
            for(int j = 0; j < 2; j++)
            {
                ans = max(ans, tree[1][i][j]);
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 4 ms 748 KB Output is correct
8 Correct 4 ms 748 KB Output is correct
9 Correct 4 ms 748 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 13 ms 748 KB Output is correct
12 Correct 13 ms 748 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 4 ms 748 KB Output is correct
8 Correct 4 ms 748 KB Output is correct
9 Correct 4 ms 748 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 13 ms 748 KB Output is correct
12 Correct 13 ms 748 KB Output is correct
13 Correct 507 ms 22804 KB Output is correct
14 Correct 456 ms 22936 KB Output is correct
15 Correct 463 ms 22764 KB Output is correct
16 Correct 538 ms 22884 KB Output is correct
17 Correct 479 ms 22764 KB Output is correct
18 Correct 439 ms 23020 KB Output is correct