oj.uz

답안 #559400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559400 2022-05-09T17:38:04 Z thecodingwizard Sjeckanje (COCI21_sjeckanje) C++11
0 / 110
 1 ms 212 KB 
/*
 * 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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -