oj.uz

답안 #367095

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367095 2021-02-16T09:10:00 Z CodePlatina Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 337 ms 21508 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tlll tuple<long long, long long, long long>
#define tiiii tuple<int, int, int, int>
#define tllll tuple<long long, long long, long long, long long>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
//#define DEBUG

using namespace std;

long long seg[808080][2][2];

void mrge(int ind)
{
    auto &nd = seg[ind], &x = seg[ind << 1], &y = seg[ind << 1 | 1];
    for(int i = 0; i < 2; ++i)
    {
        for(int j = 0; j < 2; ++j)
        {
            nd[i][j] = max(x[i][0] + y[0][j], x[i][1] + y[1][j]);
        }
    }
}

void init(const int *B, int ind, int s, int e)
{
    if(s + 1 == e)
    {
        if(B[s] < 0) seg[ind][0][0] = -B[s];
        else seg[ind][1][1] = B[s];
        return;
    }

    int mid = s + e >> 1;
    init(B, ind << 1, s, mid);
    init(B, ind << 1 | 1, mid, e);
    mrge(ind);
}

void upd(int ind, int s, int e, int pos, int x)
{
    if(s + 1 == e)
    {
        for(int i = 0; i < 2; ++i) for(int j = 0; j < 2; ++j) seg[ind][i][j] = 0;
        if(x < 0) seg[ind][0][0] = -x;
        else seg[ind][1][1] = x;
        return;
    }

    int mid = s + e >> 1;
    if(pos < mid) upd(ind << 1, s, mid, pos, x);
    else upd(ind << 1 | 1, mid, e, pos, x);
    mrge(ind);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, T; cin >> n >> T;
    int A[n]; for(auto &i : A) cin >> i;
    int B[n - 1]; for(int i = 0; i < n - 1; ++i) B[i] = A[i + 1] - A[i];
    init(B, 1, 0, n - 1);

    #ifdef DEBUG
        cout << endl;
        cout << "seg" << endl;
        for(int i = 0; i < 4 * n; ++i)
        {
            cout << i << ' ';
            for(int j = 0; j < 2; ++j)
                for(int k = 0; k < 2; ++k)
                cout << seg[i][j][k] << ' ';
            cout << endl;
        }
        cout << endl;
    #endif


    while(T--)
    {
        int l, r, x; cin >> l >> r >> x; l -= 2; --r;
        if(l >= 0) upd(1, 0, n - 1, l, B[l] += x);
        if(r < n - 1) upd(1, 0, n - 1, r, B[r] -= x);

        #ifdef DEBUG
            cout << endl;
            cout << "B" << endl;
            for(int i = 0; i < n - 1; ++i) cout << B[i] << ' '; cout << endl;
            cout << endl;
        #endif

        #ifdef DEBUG
            cout << endl;
            cout << "seg" << endl;
            for(int i = 0; i < 4 * n; ++i)
            {
                cout << i << ' ';
                for(int j = 0; j < 2; ++j)
                    for(int k = 0; k < 2; ++k)
                    cout << seg[i][j][k] << ' ';
                cout << endl;
            }
            cout << endl;
        #endif

        cout << max({ seg[1][0][0], seg[1][0][1], seg[1][1][0], seg[1][1][1] }) << '\n';
    }
}

Compilation message

Main.cpp: In function 'void init(const int*, int, int, int)':
Main.cpp:45:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int mid = s + e >> 1;
      |               ~~^~~
Main.cpp: In function 'void upd(int, int, int, int, int)':
Main.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = s + e >> 1;
      |               ~~^~~

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 1 ms 364 KB Output is correct
5 Correct 1 ms 384 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 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 4 ms 620 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 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 337 ms 21168 KB Output is correct
14 Correct 329 ms 21508 KB Output is correct
15 Correct 332 ms 21284 KB Output is correct
16 Correct 328 ms 21228 KB Output is correct
17 Correct 327 ms 21268 KB Output is correct
18 Correct 330 ms 21356 KB Output is correct