/*
* 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
