oj.uz

Submission #989416

# Submission time Handle Problem Language Result Execution time Memory
989416 2024-05-28T06:43:31 Z HuyAT Sjeckanje (COCI21_sjeckanje) C++14
15 / 110
 2000 ms 4652 KB 
#include<bits/stdc++.h>
#define newl '\n'

const int N = 2e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;

long long a[N + 1],n,q;
long long diff[N + 1],f[N + 1];

void readData(){
    std::cin >> n >> q;
    for(int i = 1;i <= n;++i){
        std::cin >> a[i];
        if(i > 1){
            diff[i - 1] = a[i] - a[i - 1];
        }
    }
}
long long calc(){
    for(int i = 1;i <= n;++i){
        f[i] = 0;
        long long mx = a[i],mn = a[i];
        for(int j = i;j >= 1;--j){
            mx = std::max(mx,a[j]);
            mn = std::min(mn,a[j]);
            f[i] = std::max(f[i],f[j - 1] + mx - mn);
        }
    }
    return f[n];
}
void update(long long &ans,int i,int x){
    if(i > 1 && i < n){
        if((diff[i - 1] < 0) != (diff[i] < 0)){
            ans += std::min(abs(diff[i - 1]),abs(diff[i]));
        }
    }
    if(i < n - 1){
        if((diff[i] < 0) != (diff[i + 1] < 0)){
            ans += std::min(abs(diff[i]),abs(diff[i + 1]));
        }
    }
    if(i < n && i > 0){
        ans -= abs(diff[i]);
    }
    diff[i] += x;
    if(i < n && i > 0){
        ans += abs(diff[i]);
    }
    if(i > 1 && i < n){
        if((diff[i - 1] < 0) != (diff[i] < 0)){
            ans -= std::min(abs(diff[i - 1]),abs(diff[i]));
        }
    }
    if(i < n - 1){
        if((diff[i] < 0) != (diff[i + 1] < 0)){
            ans -= std::min(abs(diff[i]),abs(diff[i + 1]));
        }
    }
}
void solve(){
//    long long ans = 0;
//    for(int i = 1;i < n;++i){
//        if(i < n - 1 && (diff[i] < 0) != (diff[i + 1] < 0)){
//            ans -= std::min(abs(diff[i]),abs(diff[i + 1]));
//        }
//        ans += abs(diff[i]);
//    }
//    std::cout << ans << newl;
    for(int i = 1;i <= q;++i){
        int l,r,x;
        std::cin >> l >> r >> x;
        for(int j = l;j <= r;++j){
            a[j] += x;
        }
        std::cout << calc() << newl;
    }
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    readData();
    solve();
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4440 KB Output is correct
2 Correct 5 ms 4440 KB Output is correct
3 Correct 5 ms 4444 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 5 ms 4440 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4440 KB Output is correct
2 Correct 5 ms 4440 KB Output is correct
3 Correct 5 ms 4444 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 5 ms 4440 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Execution timed out 2027 ms 4652 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4440 KB Output is correct
2 Correct 5 ms 4440 KB Output is correct
3 Correct 5 ms 4444 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 5 ms 4440 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Execution timed out 2027 ms 4652 KB Time limit exceeded
8 Halted 0 ms 0 KB -