Submission #559400

#	Time	Username	Problem	Language	Result	Execution time	Memory
559400		thecodingwizard	Sjeckanje (COCI21_sjeckanje)	C++11	0 / 110	1 ms	212 KiB

Main

/*
 * all sequences are increasing or decreasing
 *
 * - store value of: left increasing right increasing, etc etc
 *   - also store left and rightmost number
 * - merges:
 *   - for each of the four combinations, we basically have four options for how to do the middle merge
 *   - increasing
 *     - check if last number and first number can form increasing / decreasing
 *   - decreasing
 *   - completely separate: increasing decreasing, and decreasing increasing
 *
 * Base case, single number:
 * - left / rightmost number is just the number itself
 * - value of everything is 0
 *
 * Merges:
 * - increasing: if L.right < R.left
 *   cur = L.AI + R.IB + abs(R.left - L.right)
 * - decreasing: similar
 *
 *
 * Slightly easier: make the array a bunch of deltas.
 * A'[i] = A[i] - A[i-1]
 * For a range, you lose the leftmost element of that range.
 *
 * - increasing: if (L.end > 0) && (R.begin > 0)
 *   cur = L.AI + R.IB + r.begin
 *
 * Update: [l, r] +x: A'[l-1] += x, A'[r] -= x (l and r are one indexed)
 */

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n, q; 
vector<ll> A;
const int maxst = 800000;
ll lft[maxst];
ll rht[maxst];
ll II[maxst];
ll ID[maxst];
ll DI[maxst];
ll DD[maxst];

int main() {
    cin >> n >> q;
    A.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    for (int i = n-1; ~i; i--) {
        A[i] = A[i] - (i==0?0:A[i-1]);
    }

    //build(1, 0, n-1);

    for (int i = 0; i < q; i++) {
        int l, r, x; cin >> l >> r >> x;

    }

    return 0;
}

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