oj.uz

Submission #385311

# Submission time Handle Problem Language Result Execution time Memory
385311 2021-04-04T04:08:56 Z nguyen31hoang08minh2003 Sjeckanje (COCI21_sjeckanje) C++14
15 / 110
 2000 ms 748 KB 
#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

const int maxN = 2e5 + 5;
const ll inf = 1e18 + 31082003;

int n, q;
ll a[maxN];

void Subtask1() {
    vector<ll> dp(n + 5, 0);
    vector<bool> vis(n + 5);
    function<ll(int)> DP = [&](const int idx) -> ll {
        if (idx > n)
            return 0;
        if (!vis[idx]) {
            ll mx = -inf, mn = inf;
            vis[idx] = true;
            dp[idx] = -inf;
            fort(i, idx, n) {
                maxi(mx, a[i]);
                mini(mn, a[i]);
                maxi(dp[idx], DP(i + 1) + mx - mn);
            }
        }
        return dp[idx];
    };
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        fort(i, l, r)
            a[i] += x;
        fort(i, 1, n)
            vis[i] = false;
        cout << DP(1) << '\n';
    }
}

struct SegmentTree {
    struct Node {
        ll mx, mn, nxt, value;
    } it[maxN << 2];
    struct Lazy {
        ll mx, mn;
        Lazy(const ll mx = -inf, const ll mn = inf): mx(mx), mn(mn) {};
    } lz[maxN << 2];
    void up(const int i) {
        it[i].value = max(it[i << 1].value, it[i << 1 | 1].value);
        it[i].nxt = max(it[i << 1].nxt, it[i << 1 | 1].nxt);
    }
    void down(const int i) {

    }
    void set_max(const int ql, const int qr, const ll val,
                 const int i = 1, const int l = 1, const int r = n) {
        if (qr < l || r < ql)
            return;
        if (ql <= l && r <= qr) {
            lz[i].mx = val;
            it[i].mx = val;
            it[i].value = val - it[i].mn + it[i].nxt;
            return;
        }
        down(i);
        const int m = l + r >> 1;
        set_max(ql, qr, val, i << 1, l, m);
        set_max(ql, qr, val, i << 1 | 1, m + 1, r);
        up(i);
    }
    void set_min(const int ql, const int qr, const ll val,
                 const int i = 1, const int l = 1, const int r = n) {
        if (qr < l || r < ql)
            return;
        if (ql <= l && r <= qr) {
            lz[i].mn = val;
            it[i].mn = val;
            it[i].value = it[i].mx - val + it[i].nxt;
            return;
        }
        down(i);
        const int m = l + r >> 1;
        set_min(ql, qr, val, i << 1, l, m);
        set_min(ql, qr, val, i << 1 | 1, m + 1, r);
        up(i);
    }
};

void Subtask2() {

}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    fort(i, 1, n)
        cin >> a[i];
    Subtask1();
    return 0;
}

Compilation message

Main.cpp: In member function 'void SegmentTree::set_max(int, int, ll, int, int, int)':
Main.cpp:86:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         const int m = l + r >> 1;
      |                       ~~^~~
Main.cpp: In member function 'void SegmentTree::set_min(int, int, ll, int, int, int)':
Main.cpp:102:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |         const int m = l + r >> 1;
      |                       ~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 364 KB Output is correct
2 Correct 40 ms 492 KB Output is correct
3 Correct 39 ms 364 KB Output is correct
4 Correct 40 ms 364 KB Output is correct
5 Correct 40 ms 420 KB Output is correct
6 Correct 40 ms 364 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 364 KB Output is correct
2 Correct 40 ms 492 KB Output is correct
3 Correct 39 ms 364 KB Output is correct
4 Correct 40 ms 364 KB Output is correct
5 Correct 40 ms 420 KB Output is correct
6 Correct 40 ms 364 KB Output is correct
7 Execution timed out 2088 ms 748 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 364 KB Output is correct
2 Correct 40 ms 492 KB Output is correct
3 Correct 39 ms 364 KB Output is correct
4 Correct 40 ms 364 KB Output is correct
5 Correct 40 ms 420 KB Output is correct
6 Correct 40 ms 364 KB Output is correct
7 Execution timed out 2088 ms 748 KB Time limit exceeded
8 Halted 0 ms 0 KB -