oj.uz

Submission #837992

# Submission time Handle Problem Language Result Execution time Memory
837992 2023-08-26T03:25:32 Z abysmal Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 2000 ms 7196 KB 
#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<iomanip>
#include<algorithm>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<deque>
#include<math.h>
#include<assert.h>
#include<string.h>

using namespace std;

const int64_t INF = (int64_t) 1e18 + 100;
const int64_t mINF = (int64_t) 1e6 * 2 + 100;
const int64_t MOD = 1e9 + 7;
const int64_t MOD2 = 998244353;
const int nbit = 31;
const int ndig = 10;
const int nchar = 26;
const int D = 4;
int dr[D] = {-1, 0, 1, 0};
int dc[D] = {0, 1, 0, -1};
const int Dk = 8;
int drk[Dk] = {2, 2, -2, -2, 1, 1, -1, -1};
int dck[Dk] = {1, -1, 1, -1, 2, -2, 2, -2};

struct Solution
{
    int n;
    int q;
    vector<int64_t> a;
    vector<int64_t> d;
    Solution() {}

    void solve()
    {
        cin >> n >> q;
        a.resize(n + 1, 0);
        d.resize(n + 1, 0);
        for(int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }

        for(int i = 1; i <= n; i++)
        {
            d[i] = a[i] - a[i - 1];
        }

        for(int i = 0; i < q; i++)
        {
            int l; int r; int x;
            cin >> l >> r >> x;
            d[l] += x;
            if(r + 1 <= n) d[r + 1] -= x;

            vector<int64_t> dp(n + 1, 0);
            for(int j = 1; j <= n; j++)
            {
                dp[j] = dp[j - 1]; // new segment start at j
                if(j >= 2) dp[j] = max(dp[j], dp[j - 2] + Abs(d[j])); // new segment start at j - 1
                if(1LL * d[j - 1] * d[j] > 0) dp[j] = max(dp[j], dp[j - 1] + Abs(d[j])); // continue segment
            }

            cout << dp[n] << "\n";
        }
    }

    void modadd(int& t1, int t2)
    {
        t1 += t2;
        if(t1 >= MOD) t1-= MOD;
        return;
    }

    void modsub(int& t1, int t2)
    {
        t1 -= t2;
        if(t1 < 0) t1 += MOD;
        return;
    }

    int modmul(int t1, int t2)
    {
        int64_t res = 1LL * t1 * t2;
        return res % MOD;
    }

    int Abs(int tmp)
    {
        if(tmp < 0) return -tmp;
        return tmp;
    }

    int MASK(int j)
    {
        return (1 << j);
    }

    int BIT(int tmp, int j)
    {
        int x = tmp & MASK(j);
        if(x != 0) return 1;
        return 0;
    }
};

void __setup()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

int main()
{
    __setup();

    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        Solution().solve();
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 36 ms 484 KB Output is correct
8 Correct 36 ms 472 KB Output is correct
9 Correct 36 ms 468 KB Output is correct
10 Correct 37 ms 512 KB Output is correct
11 Correct 37 ms 588 KB Output is correct
12 Correct 32 ms 596 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 216 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 36 ms 484 KB Output is correct
8 Correct 36 ms 472 KB Output is correct
9 Correct 36 ms 468 KB Output is correct
10 Correct 37 ms 512 KB Output is correct
11 Correct 37 ms 588 KB Output is correct
12 Correct 32 ms 596 KB Output is correct
13 Execution timed out 2032 ms 7196 KB Time limit exceeded
14 Halted 0 ms 0 KB -