# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
794941 | 2023-07-27T04:17:28 Z | Amylopectin | Sjeckanje (COCI21_sjeckanje) | C++14 | 305 ms | 29548 KB |
#include <stdio.h> #include <iostream> #include <vector> using namespace std; const long long mxn = 1e6 + 10; long long hei[mxn] = {},dif[mxn] = {},sta[mxn][2] = {},se[mxn][2][2] = {}; long long ab(long long l) { if(l < 0) { return -l; } return l; } long long bui(long long cl,long long cr,long long no) { if(cl == cr) { se[no][0][0] = 0; se[no][0][1] = 0; se[no][1][0] = 0; se[no][1][1] = ab(dif[cl]); // sta[no][0] = 1; // sta[no][1] = 1; return 0; } long long i,j,mid = (cl+cr) / 2; bui(cl,mid,no*2); bui(mid+1,cr,no*2+1); if(dif[mid] * dif[mid+1] >= 0) { for(i=0; i<2; i++) { for(j=0; j<2; j++) { se[no][i][j] = se[no*2][i][1] + se[no*2+1][1][j]; if(j > 0) { se[no][i][j] = max(se[no][i][j],se[no][i][0]); } if(i > 0) { se[no][i][j] = max(se[no][i][j],se[no][0][j]); } } } } else { for(i=0; i<2; i++) { for(j=0; j<2; j++) { se[no][i][j] = max(se[no*2][i][0] + se[no*2+1][1][j] ,se[no*2][i][1] + se[no*2+1][0][j]); if(j > 0) { se[no][i][j] = max(se[no][i][j],se[no][i][0]); } if(i > 0) { se[no][i][j] = max(se[no][i][j],se[no][0][j]); } } } } return 0; } long long ad(long long cl,long long cr,long long no,long long tar) { if(cl > tar || cr < tar) { return 0; } if(cl == cr) { se[no][0][0] = 0; se[no][0][1] = 0; se[no][1][0] = 0; se[no][1][1] = ab(dif[cl]); // sta[no][0] = 1; // sta[no][1] = 1; return 0; } long long i,j,mid = (cl+cr) / 2; ad(cl,mid,no*2,tar); ad(mid+1,cr,no*2+1,tar); if(dif[mid] * dif[mid+1] >= 0) { for(i=0; i<2; i++) { for(j=0; j<2; j++) { se[no][i][j] = se[no*2][i][1] + se[no*2+1][1][j]; if(j > 0) { se[no][i][j] = max(se[no][i][j],se[no][i][0]); } if(i > 0) { se[no][i][j] = max(se[no][i][j],se[no][0][j]); } } } } else { for(i=0; i<2; i++) { for(j=0; j<2; j++) { se[no][i][j] = max(se[no*2][i][0] + se[no*2+1][1][j] ,se[no*2][i][1] + se[no*2+1][0][j]); if(j > 0) { se[no][i][j] = max(se[no][i][j],se[no][i][0]); } if(i > 0) { se[no][i][j] = max(se[no][i][j],se[no][0][j]); } } } } return 0; } int main() { long long i,j,n,m,q,k,cn,cm,fn,fm,cl,cr,cva; scanf("%lld %lld",&n,&q); for(i=0; i<n; i++) { scanf("%lld",&hei[i]); if(i > 0) { dif[i-1] = hei[i] - hei[i-1]; } } bui(0,n-2,1); for(i=0; i<q; i++) { scanf("%lld %lld %lld",&cl,&cr,&cva); cl --; cr --; if(cl > 0) { dif[cl-1] += cva; ad(0,n-2,1,cl-1); } if(cr < n-1) { dif[cr] -= cva; ad(0,n-2,1,cr); } printf("%lld\n",se[1][1][1]); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 292 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 292 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 3 ms | 596 KB | Output is correct |
8 | Correct | 3 ms | 724 KB | Output is correct |
9 | Correct | 3 ms | 724 KB | Output is correct |
10 | Correct | 3 ms | 724 KB | Output is correct |
11 | Correct | 3 ms | 724 KB | Output is correct |
12 | Correct | 4 ms | 724 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 0 ms | 292 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 3 ms | 596 KB | Output is correct |
8 | Correct | 3 ms | 724 KB | Output is correct |
9 | Correct | 3 ms | 724 KB | Output is correct |
10 | Correct | 3 ms | 724 KB | Output is correct |
11 | Correct | 3 ms | 724 KB | Output is correct |
12 | Correct | 4 ms | 724 KB | Output is correct |
13 | Correct | 284 ms | 28928 KB | Output is correct |
14 | Correct | 305 ms | 28892 KB | Output is correct |
15 | Correct | 300 ms | 28952 KB | Output is correct |
16 | Correct | 303 ms | 28804 KB | Output is correct |
17 | Correct | 292 ms | 28820 KB | Output is correct |
18 | Correct | 270 ms | 29548 KB | Output is correct |