Cerinta completa
Alice purchased an array of wooden boxes that she indexed from to . On each box , she writes an integer that we’ll refer to as .
Alice wants you to perform operations on the array of boxes. Each operation is in one of the following forms:
(Note: For each type of operations, )
1 l r c: Add to each . Note that can be negative.2 l r d: Replace each with .3 l r: Print the minimum value of any .4 l r: Print the sum of all .
Recall that is the maximum integer such that (e.g., and ).
Given , the value of each , and operations, can you perform all the operations efficiently?
Input Format
The first line contains two space-separated integers denoting the respective values of (the number of boxes) and (the number of operations).
The second line contains space-separated integers describing the respective values of (i.e., the integers written on each box).
Each of the subsequent lines describes an operation in one of the four formats defined above.
Constraints
Output Format
For each operation of type or type , print the answer on a new line.
Sample Input 0
10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9
Sample Output 0
-2
-2
-2
-2
0
1
1
Explanation 0
Initially, the array of boxes looks like this:
We perform the following sequence of operations on the array of boxes:
-
The first operation is
1 0 4 1, so we add to each where :
-
The second operation is
1 5 9 1, so we add to each where :
- The third operation is
2 0 9 3, so we divide each where by and take the floor:
- The fourth operation is
3 0 9, so we print the minimum value of for , which is the result of . - The fifth operation is
4 0 9, so we print the sum of for , which is the result of .
… and so on.
Limbajul de programare folosit: cpp14
Cod:
#include<stdio.h>
#define N 110000
#define M 550000
long long tmp[M], mi[M], mx[M], sum[M];
void tpl(int v, long long c, int len)
{
tmp[v] += c;
sum[v] += c * len;
mx[v] += c;
mi[v] += c;
}
void update(int v, int l, int r)
{
if(tmp[v])
{
int mid = ( l + r ) / 2;
tpl(v+v, tmp[v], mid-l+1);
tpl(v+v+1, tmp[v], r-mid);
tmp[v] = 0;
}
}
int min(int a, int b)
{
return a < b ? a : b;
}
int max(int a, int b)
{
return a > b ? a : b;
}
void add(int l, int r, int v, int x, int y, long long c)
{
if( l == x && r == y )
{
tmp[v] += c;
sum[v] += c * ( r - l + 1 );
mx[v] += c;
mi[v] += c;
return;
}
else
{
update(v, l, r);
}
int mid = ( l + r ) / 2;
if( y <= mid )
{
add(l, mid, v+v, x, y, c);
}
else if( x > mid )
{
add(mid+1, r, v+v+1, x, y, c);
}
else
{
add(l, mid, v+v, x, mid, c), add(mid+1, r, v+v+1, mid+1, y, c);
}
sum[v] = sum[v+v] + sum[v+v+1];
mi[v] = min(mi[v+v], mi[v+v+1]);
mx[v] = max(mx[v+v], mx[v+v+1]);
}
const long long inf = 5e9;
int cnt;
void div(int l, int r, int v, int x, int y, long long c)
{
cnt++;
if( l == x && r == y && mi[v] >= mx[v]-1 && ( ( mi[v] + c * inf ) / c - inf - mi[v] ) == ( ( mx[v] + c * inf ) / c - inf - mx[v] ) )
{
if( mi[v] > 0 )
{
c = mi[v] / c - mi[v];
}
else
{
c = ( mi[v] + c * inf ) / c - inf - mi[v];
}
tmp[v] += c;
sum[v] += c * ( r - l + 1 );
mx[v] += c;
mi[v] += c;
return;
}
update(v, l, r);
int mid = ( l + r ) / 2;
if( y <= mid )
{
div(l, mid, v+v, x, y, c);
}
else if( x > mid )
{
div(mid+1, r, v+v+1, x, y, c);
}
else
{
div(l, mid, v+v, x, mid, c), div(mid+1, r, v+v+1, mid+1, y, c);
}
sum[v] = sum[v+v] + sum[v+v+1];
mi[v] = min(mi[v+v], mi[v+v+1]);
mx[v] = max(mx[v+v], mx[v+v+1]);
}
long long minmize(int l, int r, int v, int x, int y)
{
if( l == x && r == y )
{
return mi[v];
}
else
{
update(v, l, r);
}
int mid = ( l + r ) / 2;
if( y <= mid )
{
return minmize(l, mid, v+v, x, y);
}
else if( x > mid )
{
return minmize(mid+1, r, v+v+1, x, y);
}
else
{
return min(minmize(l, mid, v+v, x, mid), minmize(mid+1, r, v+v+1, mid+1, y));
}
}
long long get(int l, int r, int v, int x, int y)
{
if( l == x && r == y )
{
return sum[v];
}
else
{
update(v, l, r);
}
int mid = ( l + r ) / 2;
if( y <= mid )
{
return get(l, mid, v+v, x, y);
}
else if( x > mid )
{
return get(mid+1, r, v+v+1, x, y);
}
else
{
return get(l, mid, v+v, x, mid) + get(mid+1, r, v+v+1, mid+1, y);
}
}
int a[N];
int main()
{
int n, q, i;
scanf("%d%d", &n, &q);
for( i = 1 ; i <= n ; i++ )
{
scanf("%d", &a[i]), add(1, n, 1, i, i, a[i]);
}
for( i = 1 ; i <= q ; i++ )
{
int ty, l, r;
scanf("%d%d%d", &ty, &l, &r);
l++;
r++;
if( ty == 1 )
{
int c;
scanf("%d", &c);
add(1, n, 1, l, r, c);
}
if( ty == 2 )
{
int c;
scanf("%d", &c);
div(1, n, 1, l, r, c);
}
else if( ty == 3 )
{
printf("%lld\n", minmize(1, n, 1, l, r));
}
if( ty == 4 )
{
printf("%lld\n", get(1, n, 1, l, r));
}
if( cnt > 1e8 )
{
a[-inf] = 100;
return -1;
}
}
return 0;
}
Scor obtinut: 1.0
Submission ID: 464654098
Link challenge: https://www.hackerrank.com/challenges/box-operations/problem