Submission #491850

#	Time	Username	Problem	Language	Result	Execution time	Memory
491850		Vectorized	Sjeckanje (COCI21_sjeckanje)	Java	0 / 110	82 ms	8976 KiB

Main

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static class Node{
        long skipl = 0, skipr = 0, skiplr = 0, skipnone = 0;
    }

    static long[] dif;
    static Node[] seg;
    static void construct(int node, int l, int r){
        if(l == r) return;
        if(r - l == 1){
            seg[node].skipnone = Math.abs(dif[l]);
            seg[node].skipl = 0;
            seg[node].skipr = 0;
            seg[node].skiplr = 0;
        }else{
            int mid = (l + r)/2;
            construct(node*2+1,l,mid);
            construct(node*2+2,mid,r);
            merge(mid, node, node*2+1, node*2+2);
        }
    }
    static void update(int node, int l, int r, int ind, long v){
        if(ind < l || r <= ind) return;
        if(r - l == 1){
            seg[node].skipnone = Math.abs(v);
            return;
        }
        int mid = (l + r)/2;
        update(node*2+1, l, mid, ind, v);
        update(node*2+2, mid, r, ind, v);
        merge(mid, node, node*2+1, node*2+2);
    }
    static void merge(int mid, int node, int lnode, int rnode){
        if((dif[mid - 1] > 0 && dif[mid] > 0) || (dif[mid - 1] < 0 && dif[mid] < 0) || (dif[mid] == 0 || dif[mid - 1] == 0)){
            seg[node].skipnone = seg[lnode].skipnone + seg[rnode].skipnone;
            seg[node].skipl = seg[lnode].skipl + seg[rnode].skipnone;
            seg[node].skipr = seg[lnode].skipnone + seg[rnode].skipr;
            seg[node].skiplr = seg[lnode].skipl + seg[rnode].skipr;
        }else{
            seg[node].skipnone = Math.max(seg[lnode].skipnone + seg[rnode].skipl, seg[lnode].skipr + seg[rnode].skipnone);
            seg[node].skipl = Math.max(seg[lnode].skipl + seg[rnode].skipr, seg[lnode].skiplr + seg[rnode].skipnone);
            seg[node].skipr = Math.max(seg[lnode].skipnone + seg[rnode].skiplr, seg[lnode].skipr + seg[rnode].skipr);
            seg[node].skiplr = Math.max(seg[lnode].skiplr + seg[rnode].skipr, seg[lnode].skipl + seg[rnode].skiplr);
        }
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), q = Integer.parseInt(st.nextToken());
        dif = new long[n];
        seg = new Node[4 * n];
        for (int i = 0; i < 4 * n; i++) seg[i] = new Node();
        dif[n - 1] = 0;
        st = new StringTokenizer(br.readLine());
        long prev = Long.parseLong(st.nextToken());
        for (int i = 0; i < n - 1; i++) {
            long cur = Long.parseLong(st.nextToken());
            dif[i] = cur - prev;
            prev = cur;
        }
        construct(0, 0, n-1);
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken()) - 1, r = Integer.parseInt(st.nextToken()) - 1;
            long v = Long.parseLong(st.nextToken());
            if(n != 1){
                if(l != 0){
                    l--;
                    dif[l] += v;
                }
                if(r != n - 1){
                    dif[r] -= v;
                }else{
                    r--;
                }
                update(0, 0, n - 1, l, dif[l]);
                update(0, 0, n - 1, r, dif[r]);
            }
            System.out.println(seg[0].skipnone);
        }
    }
}

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