oj.uz

Submission #870385

# Submission time Handle Problem Language Result Execution time Memory
870385 2023-11-07T14:32:03 Z fanwen Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 791 ms 66704 KB 
#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(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 FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

const int MAX = 2e5 + 5;
const long long INF = 1e18;

struct node {
    long long a[3][3];
    node() {
        memset(a, -0x3f, sizeof a);
        a[2][2] = 0;

    }
    node (long long val) {
        memset(a, -0x3f, sizeof a);
        a[2][0] = a[0][2] = val;
        a[2][1] = a[1][2] = - val;
        a[2][2] = 0;
    }

    auto & operator [] (int i) { return a[i]; }
    const auto & operator [] (int i) const { return a[i]; }

    void update(long long val) {
        REP(i, 3) REP(j, 3) a[i][j] += (i != 2) * (i == 0 ? val : -val) + (j != 2) * (j == 0 ? val : -val);
    }

    long long get_ans() {
        return a[2][2];
    }
};

int get_code(int i) {
    return i == 2 ? 2 : 1 ^ i;
}

node operator + (const node &lhs, const node &rhs) {
    node ans;
    REP(i, 3) REP(j, 3) {
        REP(k, 3) {
            maximize(ans[i][j], lhs[i][k] + rhs[get_code(k)][j]);
        }
        maximize(ans[i][j], max(lhs[i][j], rhs[i][j]));
    }
    return ans;
}

ostream & operator << (ostream &out, const node &res) {
    REP(i, 3) REP(j, 3) out << res[i][j] << " \n"[j == 2];
    return out;
}

node it[4 * MAX];
long long lazy[4 * MAX];

int n, q, a[MAX];

void build(int idx, int l, int r) {
    if(l == r) it[idx] = node(a[l]);
    else {
        int mid = l + r >> 1;
        build(idx << 1, l, mid);
        build(idx << 1 | 1, mid + 1, r);
        it[idx] = it[idx << 1] + it[idx << 1 | 1];
    }
}

void push(int idx) {
    if(lazy[idx] == 0) return;
    it[idx << 1].update(lazy[idx]);
    it[idx << 1 | 1].update(lazy[idx]);

    lazy[idx << 1] += lazy[idx], lazy[idx << 1 | 1] += lazy[idx];
    lazy[idx] = 0;
}

void update(int idx, int l, int r, int u, int v, int val) {
    if(l > v || r < u) return;
    if(l >= u && r <= v) {
        it[idx].update(val);
        lazy[idx] += val;
        return;
    }

    push(idx);

    int mid = l + r >> 1;

    update(idx << 1, l, mid, u, v, val);
    update(idx << 1 | 1, mid + 1, r, u, v, val);

    it[idx] = it[idx << 1] + it[idx << 1 | 1];
}

void you_make_it(void) {
    cin >> n >> q;
    FOR(i, 1, n) cin >> a[i];
    build(1, 1, n);

    while(q--) {
        int l, r, x; cin >> l >> r >> x;
        update(1, 1, n, l, r, x);
        cout << it[1].get_ans() << '\n';
    }
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    file("sjeckanje");
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:75:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'void update(int, int, int, int, int, int)':
Main.cpp:101:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |     int mid = l + r >> 1;
      |               ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:13:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:127:5: note: in expansion of macro 'file'
  127 |     file("sjeckanje");
      |     ^~~~
Main.cpp:13:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:127:5: note: in expansion of macro 'file'
  127 |     file("sjeckanje");
      |     ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 59480 KB Output is correct
2 Correct 9 ms 59480 KB Output is correct
3 Correct 8 ms 59484 KB Output is correct
4 Correct 8 ms 59484 KB Output is correct
5 Correct 9 ms 59340 KB Output is correct
6 Correct 8 ms 59484 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 59480 KB Output is correct
2 Correct 9 ms 59480 KB Output is correct
3 Correct 8 ms 59484 KB Output is correct
4 Correct 8 ms 59484 KB Output is correct
5 Correct 9 ms 59340 KB Output is correct
6 Correct 8 ms 59484 KB Output is correct
7 Correct 14 ms 59484 KB Output is correct
8 Correct 13 ms 59484 KB Output is correct
9 Correct 14 ms 59572 KB Output is correct
10 Correct 15 ms 59488 KB Output is correct
11 Correct 16 ms 59620 KB Output is correct
12 Correct 14 ms 59484 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 59480 KB Output is correct
2 Correct 9 ms 59480 KB Output is correct
3 Correct 8 ms 59484 KB Output is correct
4 Correct 8 ms 59484 KB Output is correct
5 Correct 9 ms 59340 KB Output is correct
6 Correct 8 ms 59484 KB Output is correct
7 Correct 14 ms 59484 KB Output is correct
8 Correct 13 ms 59484 KB Output is correct
9 Correct 14 ms 59572 KB Output is correct
10 Correct 15 ms 59488 KB Output is correct
11 Correct 16 ms 59620 KB Output is correct
12 Correct 14 ms 59484 KB Output is correct
13 Correct 691 ms 66684 KB Output is correct
14 Correct 700 ms 66644 KB Output is correct
15 Correct 791 ms 66592 KB Output is correct
16 Correct 735 ms 66704 KB Output is correct
17 Correct 684 ms 66528 KB Output is correct
18 Correct 669 ms 66664 KB Output is correct