oj.uz

Submission #874820

# Submission time Handle Problem Language Result Execution time Memory
874820 2023-11-17T21:06:37 Z vjudge1 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 404 ms 28704 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int seg[800100][2][2], arr[200100];
void merge(int n, int mid) {
	for (int i=0;i<2;i++)
	    for (int j=0;j<2;j++) {
		    seg[n][i][j]=-1e18;
		    for (int k=0;k<2;k++)
		        for (int l=0;l<2;l++)
		            if (l!=1||k!=1||arr[mid]*arr[mid+1]>=0)
		                seg[n][i][j]=max(seg[n][i][j],seg[n*2][i][k]+seg[n*2+1][l][j]);
	    }
}
void upd(int p,int l,int r,int pos) {
	if (l==r) {
		seg[p][1][1]=abs(arr[l]);
		return;
	}
	int mid=l+r>>1;
	if (pos<=mid)
	    upd(p*2,l,mid,pos);
	else
	    upd(p*2+1,mid+1,r,pos);
	merge(p,mid);
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    for(int i = n; --i;)
        arr[i+1]-=arr[i], upd(1,1,n,i+1);
    arr[1]=0;
    for(int i = 0; i < q; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        if(l!=1)
            arr[l]+=x,
            upd(1,1,n,l);
        if(r!=n)
            arr[r+1]-=x,
            upd(1,1,n,r+1);
        cout << max(max(seg[1][0][0],seg[1][0][1]),max(seg[1][1][0],seg[1][1][1])) << '\n';
    }
}

Compilation message

Main.cpp: In function 'void upd(long long int, long long int, long long int, long long int)':
Main.cpp:20:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |  int mid=l+r>>1;
      |          ~^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2512 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2512 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 5 ms 2648 KB Output is correct
9 Correct 4 ms 2652 KB Output is correct
10 Correct 4 ms 2652 KB Output is correct
11 Correct 4 ms 2648 KB Output is correct
12 Correct 4 ms 2672 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2512 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 5 ms 2648 KB Output is correct
9 Correct 4 ms 2652 KB Output is correct
10 Correct 4 ms 2652 KB Output is correct
11 Correct 4 ms 2648 KB Output is correct
12 Correct 4 ms 2672 KB Output is correct
13 Correct 382 ms 28220 KB Output is correct
14 Correct 403 ms 28144 KB Output is correct
15 Correct 391 ms 27988 KB Output is correct
16 Correct 392 ms 27988 KB Output is correct
17 Correct 404 ms 28032 KB Output is correct
18 Correct 338 ms 28704 KB Output is correct