oj.uz

Submission #545847

# Submission time Handle Problem Language Result Execution time Memory
545847 2022-04-05T15:11:42 Z Soul234 Sjeckanje (COCI21_sjeckanje) C++14
110 / 110
 747 ms 28172 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a = b, 1 : 0;
}

constexpr int sgn(ll x) { if(x == 0) return 0; return x < 0 ? -1 : 1; }
const ll INF = 1e18;
const int MX = 1<<18;
int N, Q;
ll Delta[MX];
ll st[2*MX][2][2];

void pull(int pos, int mid) {
    int lf = pos<<1, rh = pos<<1|1;
    memset(st[pos], -0x3f, sizeof st[pos]);
    F0R(a,2) F0R(b,2) F0R(c,2) F0R(d,2) {
        if(b && c) {
            if(sgn(Delta[mid]) * sgn(Delta[mid+1]) >= 0) ckmax(st[pos][a][d], st[lf][a][b] + st[rh][c][d]);
        }
        else ckmax(st[pos][a][d], st[lf][a][b] + st[rh][c][d]);
    }
}

void build(int ind = 1, int L = 1, int R = N-1) {
    if(L == R) {
        st[ind][0][0] = 0;
        st[ind][1][0] = st[ind][0][1] = -INF;
        st[ind][1][1] = llabs(Delta[L]);
    }
    else {
        int mid = (L + R) >> 1;
        build(ind<<1, L, mid);
        build(ind<<1|1, mid+1, R);
        pull(ind, mid);
    }
}

void upd(int id, ll val, int ind=1, int L = 1, int R = N-1) {
    if(L == R) {
        st[ind][0][0] = 0;
        st[ind][1][0] = st[ind][0][1] = -INF;
        st[ind][1][1] = llabs(Delta[L]);
    }
    else {
        int mid = (L + R) >> 1;
        if(id > mid) upd(id, val, ind<<1|1, mid+1, R);
        else upd(id, val, ind<<1, L, mid);
        pull(ind, mid);
    }
}

void solve() {
    cin>>N>>Q;
    ll pre;
    F0R(i,N) {
        ll cur; cin>>cur;
        if(i) Delta[i] = cur - pre;
        pre = cur;
    }
    memset(st, -0x3f, sizeof st);
    build();
    while(Q-->0) {
        int l, r;
        ll x;
        cin>>l>>r>>x;
        Delta[l-1] += x;
        Delta[r] -= x;
        if(l) upd(l-1, x);
        if(r<N) upd(r, -x);
        ll ans = -INF;
        F0R(a,2) F0R(b,2) ckmax(ans, st[1][a][b]);
        cout << ans << nl;
    }
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16660 KB Output is correct
3 Correct 8 ms 16672 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 8 ms 16664 KB Output is correct
6 Correct 8 ms 16752 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16660 KB Output is correct
3 Correct 8 ms 16672 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 8 ms 16664 KB Output is correct
6 Correct 8 ms 16752 KB Output is correct
7 Correct 13 ms 16752 KB Output is correct
8 Correct 13 ms 16764 KB Output is correct
9 Correct 13 ms 16788 KB Output is correct
10 Correct 13 ms 16724 KB Output is correct
11 Correct 14 ms 16724 KB Output is correct
12 Correct 14 ms 16724 KB Output is correct

Subtask #3
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 7 ms 16660 KB Output is correct
3 Correct 8 ms 16672 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 8 ms 16664 KB Output is correct
6 Correct 8 ms 16752 KB Output is correct
7 Correct 13 ms 16752 KB Output is correct
8 Correct 13 ms 16764 KB Output is correct
9 Correct 13 ms 16788 KB Output is correct
10 Correct 13 ms 16724 KB Output is correct
11 Correct 14 ms 16724 KB Output is correct
12 Correct 14 ms 16724 KB Output is correct
13 Correct 736 ms 25340 KB Output is correct
14 Correct 716 ms 27492 KB Output is correct
15 Correct 729 ms 27472 KB Output is correct
16 Correct 714 ms 27364 KB Output is correct
17 Correct 747 ms 27260 KB Output is correct
18 Correct 622 ms 28172 KB Output is correct