oj.uz

Submission #477568

# Submission time Handle Problem Language Result Execution time Memory
477568 2021-10-02T16:05:19 Z ljuba Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 846 ms 50752 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef vector<int> vi;
typedef vector<ll> vll;
 
typedef vector<vi> vvi;
typedef vector<vll> vvll;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
typedef vector<pii> vpii;
typedef vector<pll> vpll;
 
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second
 
template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}
 
namespace debug {
    void __print(int x) {cerr << x;}
    void __print(long long x) {cerr << x;}
    void __print(double x) {cerr << x;}
    void __print(long double x) {cerr << x;}
    void __print(char x) {cerr << '\'' << x << '\'';}
    void __print(const string &x) {cerr << '\"' << x << '\"';}
    void __print(const char *x) {cerr << '\"' << x << '\"';}
    void __print(bool x) {cerr << (x ? "true" : "false");}
 
    template<typename T, typename V>
    void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
    template<typename T>
    void __print(const T &x) {int f = 0; cerr << '{'; for(auto z : x) cerr << (f++ ? "," : ""), __print(z); cerr << "}";}
    void _print() {cerr << "]\n";}
    template <typename T, typename... V>
    void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);}
 
#ifdef ljuba
#define dbg(x...) cerr << "\e[91m" << "LINE(" << __LINE__ << ") -> " << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
}
 
using namespace debug;
 
const char nl = '\n';
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
/*
погледај сампле тестове, пре него што имплементираш (можда имаш погрешну идеју) 
уместо да разматраш неке глупе случајеве на папиру, размишљај заправо о задатку
*/

struct node {
    ll ans[2][2];
    ll prvi, posl;
};

const int mxN = 2e5 + 12;
const ll INF = 1e18 + 12;

node merge(const node &a, const node &b) {
    bool ok1 = (a.posl > 0);
    bool ok2 = (b.prvi > 0);

    node ans;
    for(int i = 0; i < 2; ++i) {
        for(int j = 0; j < 2; ++j) {
            ans.ans[i][j] = -INF;
        }
    }
    ans.prvi = a.prvi;
    ans.posl = b.posl;

    for(int i = 0; i < 2; ++i) {
        for(int j = 0; j < 2; ++j) {
            for(int k = 0; k < 2; ++k) {
                for(int l = 0; l < 2; ++l) {
                    if(ok1^ok2) {
                        //moraju biti razliciti
                        if(j == 0 && k == 0)
                            continue;
                        ckmax(ans.ans[i][l], a.ans[i][j] + b.ans[k][l]);
                    } else {
                        ckmax(ans.ans[i][l], a.ans[i][j] + b.ans[k][l]);
                    }
                }
            }
        }
    }

    return ans;
}

class SegmentTree {
private:
    int n;
    node st[4*mxN];

    void build(const vll &v, int i, int l2, int r2) {
        if(l2 == r2) {
            st[i].prvi = v[l2];
            st[i].posl = v[l2];
            st[i].ans[0][0] = llabs(v[l2]);
            st[i].ans[0][1] = st[i].ans[1][0] = -INF;
            st[i].ans[1][1] = 0;
            return;
        }

        int m2 = (l2 + r2) / 2;
        build(v, 2*i, l2, m2);
        build(v, 2*i+1, m2+1, r2);
        st[i] = merge(st[2*i], st[2*i+1]);
    }

    void update(int l1, ll x, int i, int l2, int r2) {
        if(l2 == r2) {
            st[i].prvi += x;
            st[i].posl += x;
            st[i].ans[0][0] = llabs(st[i].prvi);
            st[i].ans[0][1] = st[i].ans[1][0] = -INF;
            st[i].ans[1][1] = 0;
            return;
        }

        int m2 = (l2 + r2) / 2;
        if(l1 <= m2) update(l1, x, 2*i, l2, m2);
        else update(l1, x, 2*i+1, m2+1, r2);
        st[i] = merge(st[2*i], st[2*i+1]);
    }

    void nz(int i, int l2, int r2) {
        if(l2 == r2) {
            int vred = st[i].prvi;
            dbg(l2, vred);
            return;
        }

        int m2 = (l2 + r2) / 2;
        nz(2*i, l2, m2);
        nz(2*i+1, m2+1, r2);
    }

public:
    SegmentTree(int _n) : n(_n) {}

    void build(const vll &v) {
        build(v, 1, 0, n-1);
    }

    void update(int l1, ll x) {
        update(l1, x, 1, 0, n-1);
    }

    ll query() {
        ll ans = -INF;
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < 2; ++j) {
                ckmax(ans, st[1].ans[i][j]);
            }
        }
        return ans;
    }

    void nz() {
        nz(1, 0, n-1);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vll v(n);
    for(auto &z : v)
        cin >> z;

    if(n == 1) {
        for(int i = 0; i < q; ++i) {
            cout << 0 << nl;
        }
        return;
    }

    vll raz(n-1);
    for(int i = 1; i < n; ++i) {
        raz[i-1] = v[i] - v[i-1];
    }

    SegmentTree st(n-1);
    st.build(raz);

    //st.nz();
    //cout << st.query() << nl;

    while(q--) {
        int l, r;
        ll x;
        cin >> l >> r >> x;
        --l, --r;
        if(l-1 >= 0) {
            st.update(l-1, x);
            //dbg("levi");
        }
        if(r <= n-2) {
            st.update(r, -x);
            //dbg("desni");
        }

        //st.nz();

        cout << st.query() << nl;
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int testCases = 1;
    //cin >> testCases;
    while(testCases--)
        solve();
}

Compilation message

Main.cpp: In member function 'void SegmentTree::nz(int, int, int)':
Main.cpp:150:17: warning: unused variable 'vred' [-Wunused-variable]
  150 |             int vred = st[i].prvi;
      |                 ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37892 KB Output is correct
2 Correct 20 ms 37892 KB Output is correct
3 Correct 18 ms 37892 KB Output is correct
4 Correct 18 ms 37840 KB Output is correct
5 Correct 17 ms 37892 KB Output is correct
6 Correct 22 ms 37868 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37892 KB Output is correct
2 Correct 20 ms 37892 KB Output is correct
3 Correct 18 ms 37892 KB Output is correct
4 Correct 18 ms 37840 KB Output is correct
5 Correct 17 ms 37892 KB Output is correct
6 Correct 22 ms 37868 KB Output is correct
7 Correct 23 ms 38028 KB Output is correct
8 Correct 24 ms 38040 KB Output is correct
9 Correct 22 ms 38000 KB Output is correct
10 Correct 23 ms 38044 KB Output is correct
11 Correct 23 ms 38008 KB Output is correct
12 Correct 30 ms 37968 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37892 KB Output is correct
2 Correct 20 ms 37892 KB Output is correct
3 Correct 18 ms 37892 KB Output is correct
4 Correct 18 ms 37840 KB Output is correct
5 Correct 17 ms 37892 KB Output is correct
6 Correct 22 ms 37868 KB Output is correct
7 Correct 23 ms 38028 KB Output is correct
8 Correct 24 ms 38040 KB Output is correct
9 Correct 22 ms 38000 KB Output is correct
10 Correct 23 ms 38044 KB Output is correct
11 Correct 23 ms 38008 KB Output is correct
12 Correct 30 ms 37968 KB Output is correct
13 Correct 846 ms 50192 KB Output is correct
14 Correct 817 ms 50156 KB Output is correct
15 Correct 826 ms 50088 KB Output is correct
16 Correct 839 ms 49980 KB Output is correct
17 Correct 819 ms 49960 KB Output is correct
18 Correct 723 ms 50752 KB Output is correct