oj.uz

Submission #1105314

# Submission time Handle Problem Language Result Execution time Memory
1105314 2024-10-26T06:50:12 Z InvMOD Sjeckanje (COCI21_sjeckanje) C++14
55 / 110
 2000 ms 19164 KB 
#include<bits/stdc++.h>

#define int long long

using namespace std;

using ll = long long;

const int N = 2e5+5;
const ll inf = 1e16;

int n, q, a[N], sub[N], dp[3][N], st[N<<2][2][2];

int get_dp()
{
    // dp[0]: sum of segment
    // dp[1]: creating segment min -> max
    // dp[2]: creating segment max -> min
    dp[0][0] = 0;
    dp[1][0] = dp[2][0] = -inf;

    for(int i = 1; i <= n; i++){
        dp[0][i] = max({dp[0][i-1], dp[1][i-1] + a[i], dp[2][i-1] - a[i]});
        dp[1][i] = max(dp[1][i-1], dp[0][i-1] - a[i]);
        dp[2][i] = max(dp[2][i-1], dp[0][i-1] + a[i]);
    }
    return dp[0][n];
}

// 0,1 is not actually sign its mean the last, first has the same sign like the first position of [L, R]
// 01: l sign is different from r sign
// 10: l sign is different from r sign again
// 11: l sign is same as r sign
// 00: same meanings as 11

void update(int id, int l, int r, int x){
    if(l == r){
        st[id][1][1] = (sub[l] < 0 ? -sub[l] : sub[l]);
        return;
    }

    int m = l+r>>1;
    update(id<<1, l, m, x);
    update(id<<1|1, m+1, r, x);

    // if mid sign and mid+1 sign is different
    if(sub[m] * sub[m+1] < 0){
        // our task is to make sure that mid sign and mid+1 sign always the same
        st[id][0][0] = max(st[id<<1][0][1] + st[id<<1|1][0][0], st[id<<1][0][0] + st[id<<1|1][1][0]);
        st[id][0][1] = max(st[id<<1][0][1] + st[id<<1|1][0][1], st[id<<1][0][0] + st[id<<1|1][1][1]);
        st[id][1][0] = max(st[id<<1][1][1] + st[id<<1|1][0][0], st[id<<1][1][0] + st[id<<1|1][1][0]);
        st[id][1][1] = max(st[id<<1][1][1] + st[id<<1|1][0][1], st[id<<1][1][0] + st[id<<1|1][1][1]);
    }
    else{
        // we can make our sign the same
        st[id][0][0] = max(st[id<<1][0][1], st[id<<1][0][0]) + max(st[id<<1|1][1][0], st[id<<1|1][0][0]);
        st[id][0][1] = max(st[id<<1][0][1], st[id<<1][0][0]) + max(st[id<<1|1][1][1], st[id<<1|1][0][1]);
        st[id][1][0] = max(st[id<<1][1][1], st[id<<1][1][0]) + max(st[id<<1|1][1][0], st[id<<1|1][0][0]);
        st[id][1][1] = max(st[id<<1][1][1], st[id<<1][1][0]) + max(st[id<<1|1][1][1], st[id<<1|1][0][1]);
    }
    return;
}

void solve()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(i-1){
            sub[i] = a[i] - a[i-1];
            update(1, 2, n, i);
        }
    }

    while(q--){
        int l,r,x; cin >> l >> r >> x;

        sub[l] += x;
        update(1, 2, n, l);

        if(r+1 <= n){
            sub[r+1] -= x;
            update(1, 2, n, r+1);
        }

        cout << max({st[1][0][0], st[1][0][1], st[1][1][0], st[1][1][1]}) <<"\n";
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message

Main.cpp: In function 'void update(long long int, long long int, long long int, long long int)':
Main.cpp:42:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int m = l+r>>1;
      |             ~^~
Main.cpp: In function 'int32_t main()':
Main.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 2 ms 2552 KB Output is correct
4 Correct 2 ms 2384 KB Output is correct
5 Correct 2 ms 2384 KB Output is correct
6 Correct 2 ms 2384 KB Output is correct
7 Correct 244 ms 4756 KB Output is correct
8 Correct 210 ms 4800 KB Output is correct
9 Correct 208 ms 4688 KB Output is correct
10 Correct 217 ms 4824 KB Output is correct
11 Correct 212 ms 4688 KB Output is correct
12 Correct 197 ms 4688 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 2 ms 2552 KB Output is correct
4 Correct 2 ms 2384 KB Output is correct
5 Correct 2 ms 2384 KB Output is correct
6 Correct 2 ms 2384 KB Output is correct
7 Correct 244 ms 4756 KB Output is correct
8 Correct 210 ms 4800 KB Output is correct
9 Correct 208 ms 4688 KB Output is correct
10 Correct 217 ms 4824 KB Output is correct
11 Correct 212 ms 4688 KB Output is correct
12 Correct 197 ms 4688 KB Output is correct
13 Execution timed out 2076 ms 19164 KB Time limit exceeded
14 Halted 0 ms 0 KB -