Submission #1275108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275108		chanhchuong123	Sjeckanje (COCI21_sjeckanje)	C++20	110 / 110	314 ms	30252 KiB

Main

#include<bits/stdc++.h>
using namespace std;

const bool multiTest = false;
#define task "C"
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(mask, i) ((mask) >> (i) & 1)

template<typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) a = b; else return 0; return 1;
}
template<typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) a = b; else return 0; return 1;
}

struct node {
    long long borders[2] = {};
    long long dp[2][2] = {};

    node(long long value = 0) {
        dp[0][0] = 0;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = abs(value);
        borders[0] = borders[1] = value;
    }
};

node combine(const node &lf, const node &rg) {
    node res;
    res.borders[0] = lf.borders[0];
    res.borders[1] = rg.borders[1];
    for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) {
        for (int k = 0; k < 2; ++k) maximize(res.dp[i][j], lf.dp[i][k] + rg.dp[k ^ 1][j]);
        maximize(res.dp[i][j], lf.dp[i][0] + rg.dp[0][j]);
        if (1LL * lf.borders[1] * rg.borders[0] > 0) maximize(res.dp[i][j], lf.dp[i][1] + rg.dp[1][j]);
    }
    return res;
}

const int MAX = 200020;
int n, q;
int a[MAX];
long long d[MAX];
node myTree[1 << 19];

void build(int id, int l, int r) {
    if (l == r) myTree[id] = node(d[l]);
    else {
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        myTree[id] = combine(myTree[id << 1], myTree[id << 1 | 1]);
    }
}

void update(int pos, int delta) {
    int id = 1, l = 1, r = n - 1;
    while (l != r) {
        int mid = l + r >> 1;
        if (pos <= mid) id <<= 1, r = mid;
        else id = id << 1 | 1, l = mid + 1;
    }
    myTree[id] = node(d[pos]);
    while (id > 1) {
        id >>= 1;
        myTree[id] = combine(myTree[id << 1], myTree[id << 1 | 1]);
    }
}

void process(void) {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (i > 1) {
            d[i - 1] = a[i] - a[i - 1];
        }
    }
    build(1, 1, n - 1);
    while (q--) {
        int l, r, x; cin >> l >> r >> x;
        if (l > 1) {
            d[l - 1] += x;
            update(l - 1, x);
        }
        if (r < n) {
            d[r] -= x;
            update(r, -x);
        }

        cout << myTree[1].dp[1][1] << '\n';
    }
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r",  stdin);
		freopen(task".out", "w", stdout);
	}

	int nTest = 1; if (multiTest) cin >> nTest;
	while (nTest--) {
		process();
	}

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:102:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |                 freopen(task".inp", "r",  stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:103:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |                 freopen(task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55