Submission #442140

#	Time	Username	Problem	Language	Result	Execution time	Memory
442140		baaloone	Sjeckanje (COCI21_sjeckanje)	C++11	0 / 110	1 ms	332 KiB

Main

#include <bits/stdc++.h>
#define fs first
#define sc second
#define MASK(i) (1LL << (i))
#define BIT(i,n) (((n) >> (i)) & 1LL)
#define forw(i, f, e, c) for (int (i) = (f); (i) <= (e); (i) += (c))
#define ford(i, e, f, c) for (int (i) = (e); (i) >= (f); (i) -= (c))
#define pf push_front
#define pb push_back
#define N 200005
#define NMOD 2
#define LOG 19
#define name "optmilk"
#define int long long

using namespace std;

typedef long long ll;
typedef long double ldb;
typedef pair <int,int> pp;
const int dx[] = {0,1,0,-1,1,1,-1,-1}, dy[] = {1,0,-1,0,-1,1,1,-1};
const char dir[] = {'R','D','L','U'};
const int mod = 1e9 + 7, base = 307;
const int MOD[] = {(int)1e9 + 2777, (int) 1e9 + 5277, (int) 1e9 + 8277};
const ll oo = 1e16;

int m,n;

struct segmenttree{
    int n;
    vector <ll> tree,mi,ma,mil,mal,mir,mar,lazy;

    segmenttree(int _n = 0){
        n = _n;
        tree.assign(4*n+5,0);
        ma.assign(4*n+5,0);
        mi.assign(4*n+5,0);
        mal.assign(4*n+5,0);
        mil.assign(4*n+5,oo);
        mar.assign(4*n+5,0);
        mir.assign(4*n+5,oo);
        lazy.assign(4*n+5,0);
    }

    void gom(int gt, int node){
        mi[node] += gt;
        ma[node] += gt;
        mil[node] += gt;
        mir[node] += gt;
        mal[node] += gt;
        mar[node] += gt;
        lazy[node] += gt;
    }

    void pushdown(int l, int r, int node){
        gom(lazy[node],node*2);
        gom(lazy[node],node*2+1);
        lazy[node] = 0;
    }

    void update(int l, int r, int x, int y, int gt, int node){
        if (l > y || r < x || r < l)return;
        if (l >= x && r <= y){
            gom(gt,node);
            return;
        }

        pushdown(l,r,node);
        int mid = (l + r) >> 1;
        update(l,mid,x,y,gt,node*2); update(mid + 1,r,x,y,gt,node*2+1);

        mi[node] = min(mi[node*2],mi[node*2+1]);
        ma[node] = max(ma[node*2],ma[node*2+1]);

        mal[node] = max(ma[node*2],mal[node*2+1]);
        mil[node] = min(mi[node*2],mil[node*2+1]);
        mar[node] = mar[node*2+1]; mir[node] = mir[node*2+1];
        tree[node] = mal[node] - mil[node] + mar[node] - mir[node];

        //if (node == 2)cout << tree[2] << endl;

        if (ma[node*2] - mi[node*2] + ma[node*2+1] - mi[node*2+1] >= tree[node]){
            tree[node] = ma[node*2] - mi[node*2] + ma[node*2+1] - mi[node*2+1];
            mal[node] = ma[node*2]; mar[node] = ma[node*2+1];
            mil[node] = mi[node*2]; mir[node] = mi[node*2+1];
        }

        if (mal[node*2] - mil[node*2] + max(mar[node*2],ma[node*2+1]) - min(mir[node*2],mi[node*2+1]) > tree[node]){
            mal[node] = mal[node*2]; mil[node] = mil[node*2];
            mar[node] = max(mar[node*2],ma[node*2+1]);
            mir[node] = min(mir[node*2],mi[node*2+1]);
            tree[node] = mal[node] - mil[node] + mar[node] - mir[node];
        }
    }

    void update(int x, int y, int gt){
        update(1,n,x,y,gt,1);
    }
};

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #ifdef CODENE
        freopen("a.inp","r",stdin); freopen("a.out","w",stdout);
    #else
        //freopen(name".in","r",stdin); freopen(name".out","w",stdout);
    #endif

    cin >> n >> m;
    segmenttree it(n);
    forw(i,1,n,1){int x; cin >> x; it.update(i,i,x);}

    while (m--){
        int x,y,gt; cin >> x >> y >> gt;
        it.update(x,y,gt);

        //cout << it.tree[2] << endl;

        cout << max(it.tree[1],it.ma[1] - it.mi[1]) << '\n';
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:6:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define forw(i, f, e, c) for (int (i) = (f); (i) <= (e); (i) += (c))
      |                                   ^
Main.cpp:112:5: note: in expansion of macro 'forw'
  112 |     forw(i,1,n,1){int x; cin >> x; it.update(i,i,x);}
      |     ^~~~

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