# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
int tree[4*N],dp[N],a[N],n;
void build(int node, int le, int ri/* int type 0-even,1-odd*/) {
if (le == ri) {
tree[node] = dp[le];
return ;
}
int mid = (le + ri) / 2;
build(2*node,le,mid);
build(2*node + 1, mid + 1, ri);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
void update(int node, int le, int ri, int idx, int val) {
if (le > idx || ri < idx) return ;
if (le == ri) {
tree[node] = val;
return ;
}
int mid = (le + ri) / 2;
update(2*node,le,mid,idx,val);
update(2*node + 1, mid + 1, ri, idx, val);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
int getans(int node, int le, int ri, int start, int end) {
if (start > end) return 0;
if (le > end || ri < start) return 0;
if (le >= start && ri <= end) return tree[node];
int mid = (le + ri) / 2;
return getans(2*node,le,mid,start,end) + getans(2*node + 1, mid + 1, ri, start, end);
}
void go(int l, int r, int val, int type) {
int prer = a[r];
int changed = 0;
int to = 0;
int prel = a[l];
if (type == 0) {
for (int i = l; i <= r; i++) {
a[i] += val;
}
}
if (type == 1) {
for (int i = l; i <= r; i++) {
a[i] *= -1;
}
}
int curl = a[l];
int curr = a[r];
int ff = 0;
if (r < n) {
if (prer > a[r + 1] && curr < a[r + 1]) changed = 1;
if (prer == a[r + 1] && curr != a[r + 1]) changed = 1;
if (prer != a[r + 1] && curr == a[r + 1]) changed = 1;
if (prer < a[r + 1] && curr > a[r + 1]) changed = 1;
}
if (changed) {
if (r == n) dp[r] = r;
else {
if (a[r] == a[r + 1]) dp[r] = r;
else dp[r] = r + 1;
}
if (r < n - 1) {
if ((a[r] > a[r + 1] && a[r + 1] < a[r + 2]) || (a[r] < a[r + 1] && a[r + 1] > a[r + 2]))
dp[r] = dp[r + 1];
}
update(1,1,n,r,dp[r]);
for (int i = r - 1; i >= 1; i--) {
if (i == n - 1) {
if (a[i] == a[i + 1]) dp[i] = i;
else dp[i] = i + 1;
} else {
if ((a[i] < a[i + 1] && a[i + 1] > a[i + 2]) || (a[i] > a[i + 1] && a[i + 1] < a[i + 2]))
dp[i] = dp[i + 1];
}
update(1,1,n,i,dp[i]);
}
}
changed = 0;
if (l > 1) {
if (prel > a[l - 1] && curl < a[l - 1]) changed = 1;
if (prel == a[l - 1] && curl != a[l - 1]) changed = 1;
if (prel != a[l - 1] && curl == a[l - 1]) changed = 1;
if (prel < a[l - 1] && curl > a[l - 1]) changed = 1;
}
//cout<<changed<<"\n";
if (changed) {
int to = getans(1,1,n,l,l);
if ((a[l - 1] > a[l] && a[l] < a[l + 1]) || (a[l - 1] < a[l] && a[l] > a[l + 1])) {
dp[l - 1] = to;
}
else {
if (a[l - 1] == a[l]) to = l - 1;
else
to = l;
dp[l - 1] = to;
}
//cout<<dp[l - 1]<<endl;
update(1,1,n, l - 1, dp[l - 1]);
for (int i = l - 2; i >= 1; i--) {
if ((a[i] < a[i + 1] && a[i + 1] > a[i + 2]) || (a[i] > a[i + 1] && a[i + 1] < a[i + 2]))
dp[i] = dp[i + 1];
else {
if (a[i] == a[i + 1]) dp[i] = i;
else dp[i] = i + 1;
}
update(1,1,n,i,dp[i]);
}
}
}
int get(int x) {
return (x*(x + 1)) / 2;
}
int getpas(int l, int r) {
int le = l;
int ri = r;
int pas = -1;
while (le <= ri) {
int mid = (le + ri) / 2;
if (getans(1,1,n,mid,mid) > r) {
ri = mid - 1;
pas = mid;
} else le = mid + 1;
}
int startsum = get(r) - get(l - 1);
int endsum = 0;
if (pas == -1) {
endsum = getans(1,1,n,l,r) + (r - l + 1);
} else {
endsum = getans(1,1,n,l,pas - 1) + (r - pas + 1)*r + (r - l + 1);
}
return endsum - startsum;
}
signed main() {
int q;
cin>>n>>q;
for (int i = 1; i <= n; i++) {
cin>>a[i];
}
dp[n] = n;
if (a[n - 1] == a[n]) dp[n - 1] = n - 1;
else
dp[n - 1] = n;
for (int i = n - 2; i >= 1; i--) {
dp[i] = i + 1;
if (a[i] == a[i + 1]) dp[i] = i;
if (a[i] > a[i + 1] && a[i + 1] < a[i + 2]) dp[i] = dp[i + 1];
if (a[i] < a[i + 1] && a[i + 1] > a[i + 2]) dp[i] = dp[i + 1];
}
build(1,1,n);
while (q--) {
char ch;
cin>>ch;
if (ch == '+') {
int l,r,val;
cin>>l>>r>>val;
go(l,r,val,0);
continue;
}
if (ch == '*') {
int l,r;
cin>>l>>r;
go(l,r,0,1);
continue;
}
if (ch == '?') {
int l,r;
cin>>l>>r;
cout<<getpas(l,r)<<endl;
continue;
}
}
}
Compilation message
Main.cpp: In function 'void go(int, int, int, int)':
Main.cpp:40:9: warning: unused variable 'to' [-Wunused-variable]
40 | int to = 0;
| ^~
Main.cpp:54:9: warning: unused variable 'ff' [-Wunused-variable]
54 | int ff = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
522 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2083 ms |
7044 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
522 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
522 ms |
424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
