# 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],n;
long long a[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 upd(int idx) {
if (idx == n) {
dp[idx] = n;
return ;
}
if (a[idx] == a[idx + 1]) dp[idx] = idx;
else dp[idx] = idx + 1;
if (idx < n - 1) {
if ((a[idx] < a[idx + 1] && a[idx + 1] > a[idx + 2]) || (a[idx] > a[idx + 1] && a[idx + 1] < a[idx + 2]))
dp[idx] = dp[idx + 1];
}
return ;
}
/*
void prnt() {
for (int i = 1; i <= n; i++) {
cout<<dp[i]<<" ";
}
cout<<"\n";
cout<<"\n";
}*/
void go(int l, int r, int val, int type) {
int prer = a[r];
int changed = 0;
int to = 0;
int prel = a[l];
// prnt();
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 (true) {
upd(r);
update(1,1,n,r,dp[r]);
for (int i = r - 1; i >= 1; i--) {
upd(i);
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 (true) {
int to = getans(1,1,n,l,l);
upd(l);
upd(l - 1);
update(1,1,n, l - 1, dp[l - 1]);
for (int i = l - 2; i >= 1; i--) {
upd(i);
update(1,1,n,i,dp[i]);
}
}
// prnt();
}
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() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int q;
cin>>n>>q;
for (int i = 1; i <= n; i++) {
cin>>a[i];
}
dp[n] = n;
upd(n);
upd(n - 1);
for (int i = n - 2; i >= 1; i--) {
upd(i);
}
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:102:13: warning: unused variable 'to' [-Wunused-variable]
102 | int to = getans(1,1,n,l,l);
| ^~
Main.cpp:61:9: warning: variable 'changed' set but not used [-Wunused-but-set-variable]
61 | int changed = 0;
| ^~~~~~~
Main.cpp:62:9: warning: unused variable 'to' [-Wunused-variable]
62 | int to = 0;
| ^~
Main.cpp:77:9: warning: unused variable 'ff' [-Wunused-variable]
77 | int ff = 0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1954 ms |
452 KB |
Output is correct |
| 2 |
Correct |
1989 ms |
452 KB |
Output is correct |
| 3 |
Correct |
1950 ms |
452 KB |
Output is correct |
| 4 |
Correct |
1947 ms |
448 KB |
Output is correct |
| 5 |
Correct |
1934 ms |
452 KB |
Output is correct |
| 6 |
Correct |
3 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1921 ms |
444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2028 ms |
7932 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1954 ms |
452 KB |
Output is correct |
| 2 |
Correct |
1989 ms |
452 KB |
Output is correct |
| 3 |
Correct |
1950 ms |
452 KB |
Output is correct |
| 4 |
Correct |
1947 ms |
448 KB |
Output is correct |
| 5 |
Correct |
1934 ms |
452 KB |
Output is correct |
| 6 |
Correct |
3 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1921 ms |
444 KB |
Output is correct |
| 8 |
Execution timed out |
2076 ms |
2516 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1954 ms |
452 KB |
Output is correct |
| 2 |
Correct |
1989 ms |
452 KB |
Output is correct |
| 3 |
Correct |
1950 ms |
452 KB |
Output is correct |
| 4 |
Correct |
1947 ms |
448 KB |
Output is correct |
| 5 |
Correct |
1934 ms |
452 KB |
Output is correct |
| 6 |
Correct |
3 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1921 ms |
444 KB |
Output is correct |
| 8 |
Execution timed out |
2028 ms |
7932 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
