Submission #681379

#	Time	Username	Problem	Language	Result	Execution time	Memory
681379		Nafeeszx	Sjeckanje (COCI21_sjeckanje)	C++14	110 / 110	443 ms	37728 KiB

Main

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define trav(a, x) for(auto& a : x)
#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define ROF(i, a, b) for (int i=(a); i>=(signed)(b); i--)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define vi vector<int>
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
typedef long long ll;

const ll mod = 1e9 + 7, MOD = 998244353;

void setIO(string name = "") { 
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(name.size()){
		freopen((name+".in").c_str(), "r", stdin);
		freopen((name+".out").c_str(), "w", stdout);
	}
}

struct item{
    ll l, r, dp[2][2];
};

struct segtree{

    int size;
    vector<item> values;

	item neut = {0, 0, {{0,0}, {0,0}}};

    void init(int n){
        size = 1;
        while(size < n) size *= 2;
        values.assign(2 * size, neut);
    }

	item single (int v) {
		return {v, v, {{0, 0}, {0, abs(v)}}};
	}

	item merge(item &x, item &y) {
		item res;
        res.l = x.l;
        res.r = y.r;
       
        F0R(l, 2) F0R(r, 2) {
            res.dp[l][r] = 0;
            F0R(o, 2) F0R(m, 2) {
            if(m == 1 && o == 1 && (x.r >= 0) != (y.l >= 0)) continue;
            res.dp[l][r] = max(res.dp[l][r], x.dp[l][m] + y.dp[o][r]);
            }
        }
        return res;
	}

    void build(vector<ll> &a, int x, int lx, int rx) {
        if(rx - lx == 1) {
            if(lx < (int)a.size()) {
                values[x] = single(a[lx]);
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(a, 2 * x + 1, lx, m);
        build(a, 2 * x + 2, m, rx);
        values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
    }

    void build(vector<ll> &a) {
        build(a, 0, 0, size);
    }

    void set(int i, ll v, int x, int lx, int rx){
        if(rx - lx == 1){
            values[x] = single(v);
            return;
        }
        int m = (lx + rx) / 2;
        if(i < m){
            set(i, v, 2 * x + 1, lx, m);
        } else {
            set(i, v, 2 * x + 2, m, rx);
        }
        values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
    }

    void set(int i, ll v){
        set(i, v, 0, 0, size);
    } 

    item calc(int l, int r, int x, int lx, int rx){
        if(lx >= r || rx <= l) return neut;
        if(l <= lx && r >= rx) return values[x];
        int m = (lx + rx) / 2;
        item s1 = calc(l, r, 2 * x + 1, lx, m);
        item s2 = calc(l, r, 2 * x + 2, m, rx);
        return merge(s1, s2);
    } 

    item calc(int l, int r){
        return calc(l, r, 0, 0, size);
    }
};

int main() 
{	
	setIO();
    int n, q; cin >> n >> q; 
    vector<ll> a(n), d(n-1);
    F0R(i, n) cin >> a[i];
    F0R(i, n-1) {
        d[i] = a[i+1] - a[i];
    }
    segtree S;
    S.init(n-1);
    S.build(d);
    //item res = S.values[0];
        /*int mx = 0;
        F0R(i, 2) F0R(j, 2) {
            mx = max(mx, res.dp[i][j]);
        }
        cout << mx << '\n';*/
        //cout << res.dp[0][0] << " " << res.dp[0][1] << " " << res.dp[1][0] << " " << res.dp[1][1] << '\n';
    while(q--) {
        ll l, r, x;
        cin >> l >> r >> x;
        l -= 2;
        r--;
        if(l >= 0) {d[l] = d[l] + x; S.set(l, d[l]);}// cout << d[l] << " ";}
        if(r < n-1){d[r] = d[r] - x; S.set(r, d[r]);}
        //cout << d[r ] << " ";}
        //cout << d[l] << d[r] << " ";
        
       
        item res = S.values[0];
        ll mx = 0;
        F0R(i, 2) F0R(j, 2) {
            mx = max(mx, res.dp[i][j]);
        }
        cout << mx << "\n";
        //cout << res.dp[0][0] << " " << res.dp[0][1] << " " << res.dp[1][0] << " " << res.dp[1][1] << '\n';
    }
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 55 / 55