oj.uz

Submission #685276

# Submission time Handle Problem Language Result Execution time Memory
685276 2023-01-23T21:05:08 Z AmirElarbi Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 598 ms 29516 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e17
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
const int MOD = 1e9+7;
const int nax = 2e5+5;
const int nax2 = 200+5;
typedef complex<int> Point;
using cd = complex<double>;
ll st[nax*4][4], diff[nax], s[nax];
void combine(int v, int l, int r){
    int md = (l+r)/2;
    
    st[v][0] = st[v][1] = st[v][2] = st[v][3] = 0;

    if((diff[md] > 0 && diff[md+1] < 0) || (diff[md] < 0 && diff[md+1] > 0)){
        st[v][0] = max(abs(st[v*2][0]) + st[v*2+1][1], st[v][0]);  
        st[v][0] = max(st[v*2][2] + abs(st[v*2+1][0]), st[v][0]);

        st[v][1] = max(st[v*2][1] + st[v*2+1][1], st[v][1]);  
        st[v][1] = max(st[v*2][3] + abs(st[v*2+1][0]), st[v][1]); 

        st[v][2] = max(abs(st[v*2][0]) + st[v*2+1][3], st[v][2]);  
        st[v][2] = max(st[v*2][2] + st[v*2+1][2], st[v][2]);  

        st[v][3] = max(st[v*2][1] + st[v*2+1][3], st[v][3]);  
        st[v][3] = max(st[v*2][3] + st[v*2+1][2], st[v][3]); 
    } else {
        st[v][0] = max(abs(st[v*2][0]) + abs(st[v*2+1][0]), st[v][0]);

        st[v][1] = max(st[v*2][1] + abs(st[v*2+1][0]), st[v][1]); 

        st[v][2] = max(abs(st[v*2][0]) + st[v*2+1][2], st[v][2]); 

        st[v][3] = max(st[v*2][1] + st[v*2+1][2], st[v][3]);    
    }
}
void build(int v, int l, int r){
    if(l == r){
        st[v][0] = diff[l];
        st[v][1] = st[v][2] = st[v][3] = 0;
        return;
    }
    int md = (l+r)/2;
    build(v*2,l,md);
    build(v*2+1,md+1,r);
    combine(v, l, r);
}
void update(int v, int l, int r, int pos, ll val){
    if(pos < l || pos > r) return;
    if(l == r){
        st[v][0] += val;
        //cout << st[v][0] << " " << diff[l] << endl;
        return;
    }
    int md = (l+r)/2;
    update(v*2,l,md,pos,val);
    update(v*2+1,md+1,r,pos,val);
    combine(v, l, r);
}
int main(){ 
    optimise;
    int n,q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i)
    {
        cin >> s[i];
    }
    for (int i = 0; i < n; ++i)
    {
        if(i) diff[i] =  s[i]-s[i-1];
        else diff[i] = 0;
    }
    build(1,0,n-1);
    while(q--){
        int l,r;
        ll x;
        cin >> l >> r >> x;
        l--,r--;
        if(l > 0){ 
            diff[l] += x;
            update(1,0,n-1,l,x);
        }
        if(r < n-1){
            diff[r+1] -= x;  
            update(1,0,n-1,r+1,-x);
        }
        cout << st[1][0] << endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 732 KB Output is correct
8 Correct 8 ms 724 KB Output is correct
9 Correct 7 ms 680 KB Output is correct
10 Correct 7 ms 676 KB Output is correct
11 Correct 7 ms 724 KB Output is correct
12 Correct 8 ms 780 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 732 KB Output is correct
8 Correct 8 ms 724 KB Output is correct
9 Correct 7 ms 680 KB Output is correct
10 Correct 7 ms 676 KB Output is correct
11 Correct 7 ms 724 KB Output is correct
12 Correct 8 ms 780 KB Output is correct
13 Correct 598 ms 28964 KB Output is correct
14 Correct 552 ms 29168 KB Output is correct
15 Correct 573 ms 28944 KB Output is correct
16 Correct 548 ms 28980 KB Output is correct
17 Correct 547 ms 28916 KB Output is correct
18 Correct 563 ms 29516 KB Output is correct