oj.uz

Submission #934503

# Submission time Handle Problem Language Result Execution time Memory
934503 2024-02-27T13:20:51 Z Whisper Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 532 ms 50836 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 3
            }
            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 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2524 KB Output is correct
4 Correct 1 ms 2396 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 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2524 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 5 ms 3164 KB Output is correct
8 Correct 5 ms 3164 KB Output is correct
9 Correct 6 ms 3040 KB Output is correct
10 Correct 5 ms 3164 KB Output is correct
11 Correct 5 ms 3120 KB Output is correct
12 Correct 5 ms 3160 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2524 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 5 ms 3164 KB Output is correct
8 Correct 5 ms 3164 KB Output is correct
9 Correct 6 ms 3040 KB Output is correct
10 Correct 5 ms 3164 KB Output is correct
11 Correct 5 ms 3120 KB Output is correct
12 Correct 5 ms 3160 KB Output is correct
13 Correct 525 ms 50236 KB Output is correct
14 Correct 508 ms 50256 KB Output is correct
15 Correct 516 ms 50256 KB Output is correct
16 Correct 532 ms 50132 KB Output is correct
17 Correct 499 ms 50000 KB Output is correct
18 Correct 441 ms 50836 KB Output is correct