// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r
#define ll long long
#define int long long
using namespace std;
const int N = 3e5 + 5;
int n, m, q, a[N];
int L, R, id;
ll vl, b[N];
struct node {
ll ans;
int pr;
int sf;
ll fr;
ll ls;
int len;
int add;
};
node v[4 * N], bs = {0, 0, 0, 0, 0, 0, 0};
node merge(node a, node b) {
node c;
c.add = 0;
c.ans = a.ans + b.ans;
c.fr = a.fr, c.ls = b.ls;
c.sf = b.sf, c.pr = a.pr;
if ((a.ls < 0 && b.fr > 0) || (a.ls > 0 && b.fr < 0)) {
if (b.sf == b.len) c.sf += a.sf;
if (a.pr == a.len) c.pr += b.pr;
c.ans += a.sf * b.pr;
}
return c;
}
void build(tree) {
if (l == r) {
v[h].len = 1;
v[h].fr = b[l];
v[h].ls = b[l];
if (v[h].fr) {
v[h].pr = v[h].sf = v[h].ans = 1;
}
return ;
}
build(left), build(right);
v[h] = merge(v[lf], v[rf]);
v[h].len = v[lf].len + v[rf].len;
}
void shift(tree) {
if (v[h].add) {
v[lf].add ^= 1, v[lf].fr *= -1; v[lf].ls *= -1;
v[rf].add ^= 1, v[rf].fr *= -1; v[rf].ls *= -1;
v[h].add = 0;
return ;
}
}
node get(tree) {
if (r < L || R < l) return bs;
if (L <= l && r <= R) return v[h];
shift(h, l, r);
return merge(get(left), get(right));
}
void upd(tree) {
if (r < id || id < l) return ;
if (l == id && id == r) {
v[h].fr += vl;
v[h].ls += vl;
if (v[h].fr) {
v[h].pr = v[h].sf = v[h].ans = 1;
}
else {
v[h].pr = v[h].sf = v[h].ans = 0;
}
return ;
}
shift(h, l, r);
upd(left), upd(right);
v[h] = merge(v[lf], v[rf]);
}
void upd_(tree) {
if (r < L || R < l) return ;
if (L <= l && r <= R) {
v[h].add ^= 1;
v[h].fr *= -1;
v[h].ls *= -1;
return ;
}
shift(h, l, r);
upd_(left), upd_(right);
v[h] = merge(v[lf], v[rf]);
}
main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (1 < i) {
b[i - 1] = a[i - 1] - a[i];
}
}
m = n - 1, build(1, 1, m);
for (int i = 1; i <= q; ++i) {
char c;
cin >> c;
if (c == '+') {
cin >> L >> R >> vl; --L;
vl = -vl, id = L; if (1 <= L) upd(1, 1, m), b[id] += vl;
vl = -vl, id = R; if (R <= m) upd(1, 1, m), b[id] += vl;
}
else
if (c == '*') {
vl = 0;
cin >> L >> R; --R;
for (int j = L; j <= R; ++j) {
b[j] *= -1;
}
build(1, 1, m);
/*
upd_(1, 1, m); ++R, --L;
id = L; if (1 <= L) upd(1, 1, m);
id = R; if (R <= m) upd(1, 1, m);*/
}
else
if (c == '?') {
cin >> L >> R; --R;
ll res = R - L + 2, tot = 0;
if (b[L]) tot = 1;
for (int j = L + 1; j <= R; ++j) {
if ((b[j - 1] > 0 && b[j] < 0) || (b[j] > 0 && b[j - 1] < 0)) {
res += tot;
++tot;
}
else
if (b[j]) {
tot = 1;
}
else
if (!b[j]) {
res += tot;
tot = 0;
}
}
if (tot) res += tot;
cout << res << "\n";
//cout << get(1, 1, m).ans + R - L + 2 << "\n";
}
}
}
Compilation message
Main.cpp:110:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
110 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
1388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2068 ms |
62956 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
1388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
1388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
