oj.uz

답안 #989729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
989729 2024-05-28T16:25:37 Z HuyAT Sjeckanje (COCI21_sjeckanje) C++14
15 / 110
 2000 ms 4444 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],b[N + 1];
int 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(){
    std::vector<long long> b;
    b.emplace_back(0);
    b.emplace_back(a[1]);
    int it = 2;
    for(int i = 2;i < n;++i){
        if((a[i - 1] < a[i]) != (a[i] < a[i + 1])){
            it = std::max(it,i - 2 + 1);
            while(it <= std::min(n,i + 2)){
//                std::cerr << it << "\n";
                b.emplace_back(a[it]);
                ++it;
            }
        }
    }
    it = std::max(it,n - 2 + 1);
    while(it <= n){
        b.emplace_back(a[it++]);
    }
//    for(int val : b){
//        std::cout << val << " ";
//    }
//    std::cout << newl;
    for(int i = 1;i < (int)b.size();++i){
        f[i] = 0;
        long long mx = b[i],mn = b[i];
        for(int j = i;j >= 1;--j){
            mx = std::max(mx,(long long)b[j]);
            mn = std::min(mn,(long long)b[j]);
            f[i] = std::max(f[i],f[j - 1] + mx - mn);
        }
    }
    return f[(int)b.size() - 1];
}
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;
        }
//        update(ans,l - 1,x);
//        update(ans,r,-x);
//        assert(calc() == ans);
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4440 KB Output is correct
2 Correct 5 ms 4444 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 5 ms 2396 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4440 KB Output is correct
2 Correct 5 ms 4444 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 5 ms 2396 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Execution timed out 2033 ms 2688 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4440 KB Output is correct
2 Correct 5 ms 4444 KB Output is correct
3 Correct 5 ms 2396 KB Output is correct
4 Correct 5 ms 2396 KB Output is correct
5 Correct 4 ms 2396 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Execution timed out 2033 ms 2688 KB Time limit exceeded
8 Halted 0 ms 0 KB -