oj.uz

Submission #934504

# Submission time Handle Problem Language Result Execution time Memory
934504 2024-02-27T13:21:31 Z Whisper Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 536 ms 44656 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define pii pair<int , int>
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 2e5 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int nArr, numQuery;
int a[MAX], d[MAX];

struct SegTree{
    struct Node{
        int f[2][2];
        int L, R;
        Node(){
            memset(f, -0x3f, sizeof f);
        }
        Node(int x){
            memset(f, -0x3f, sizeof f);
            f[1][1] = abs(x);
            f[0][0] = 0;
            if (x < 0) L = R = -1;
            else if (x > 0) L = R = 1;
            else L = R = 0;
        }
        friend Node operator + (const Node& a, const Node& b){
            Node res;
            res.L = a.L, res.R = b.R;
            REP(x, 2) REP(y, 2){
                REP(l, 2) REP(r, 2){
                    if (l ^ r){
                        maximize(res.f[x][y], a.f[x][l] + b.f[r][y]);
                        //Merge lại thành 1 nhóm có độ dài 2
                    }
                }
                maximize(res.f[x][y], a.f[x][0] + b.f[0][y]);
                if (a.R * b.L >= 0) maximize(res.f[x][y], a.f[x][1] + b.f[1][y]);
                // Merge lại thành 1 nhóm có độ dài >= 2
            }
            return res;
        }
    };
    vector<Node> st;
    int n;
    SegTree(int _n){
        this -> n = _n;
        st.resize((n << 2));
    }
    void modify(int id, int l, int r, int p){
        if (p < l || p > r) return;
        if (l == r){
            st[id] = Node(d[p]);
            return;
        }
        int mid = (l + r) >> 1;
        modify(id << 1, l, mid, p);
        modify(id << 1 | 1, mid + 1, r, p);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }
    int query(int node){
        int ans = 0;
        REP(l, 2) REP(r, 2){
            maximize(ans, st[node].f[l][r]);
        }
        return ans;
    }
};

void Whisper(){
    cin >> nArr >> numQuery;
    for (int i = 1; i <= nArr; ++i) cin >> a[i];
    SegTree st(nArr);
    --nArr;
    for (int i = 1; i <= nArr; ++i){
        d[i] = a[i + 1] - a[i];
        st.modify(1, 1, nArr, i);
    }
    for (int i = 1; i <= numQuery; ++i){
        int l, r, x; cin >> l >> r >> x;
        d[l - 1] += x;
        d[r] -= x;
        st.modify(1, 1, nArr, l - 1);
        st.modify(1, 1, nArr, r);
        cout << st.query(1) << '\n';
    }
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 6 ms 3160 KB Output is correct
8 Correct 6 ms 2908 KB Output is correct
9 Correct 5 ms 3164 KB Output is correct
10 Correct 6 ms 2908 KB Output is correct
11 Correct 5 ms 3164 KB Output is correct
12 Correct 5 ms 2908 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 6 ms 3160 KB Output is correct
8 Correct 6 ms 2908 KB Output is correct
9 Correct 5 ms 3164 KB Output is correct
10 Correct 6 ms 2908 KB Output is correct
11 Correct 5 ms 3164 KB Output is correct
12 Correct 5 ms 2908 KB Output is correct
13 Correct 521 ms 44372 KB Output is correct
14 Correct 536 ms 44656 KB Output is correct
15 Correct 526 ms 43856 KB Output is correct
16 Correct 521 ms 44020 KB Output is correct
17 Correct 522 ms 44236 KB Output is correct
18 Correct 435 ms 44116 KB Output is correct