Submission #1029490

---

Source Code Expand

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

struct Seg {
    bool ok;
    LL val[4][4][2][2]; // [L][R][len][top]
    Seg() {
	ok = false;
	memset(val, 0xc0, sizeof val);
    }
    Seg(int v_) { // singleton
	ok = true;
	memset(val, 0xc0, sizeof val);
	REP (L, 4) REP (R, 4) {
	    if ((L>>1) == (R & 1)) {
		int len = (L & 1) || ((R >> 1) == 0);
		if (R & 1) { // right
		    if (len == 0) {
			val[L][R][0][0] = 0;
			val[L][R][0][1] = v_;
		    } else {
			val[L][R][1][0] = v_;
			val[L][R][1][1] = 0;
		    }
		} else { // left
		    val[L][R][len][0] = v_;
		    val[L][R][len][1] = 0;
		}
	    }
	}
    }
};

Seg operator*(const Seg &x, const Seg &y) {
    if (!x.ok) return y;
    if (!y.ok) return x;
    // TODO: do stuff something
    Seg z;
    z.ok = true;
    REP (L, 4) REP (C, 4) REP (R, 4) REP (len_x, 2) REP (len_y, 2) REP (top_x, 2) {
	int len = len_x ^ len_y;
	LL tmp = x.val[L][C][len_x][top_x];
	tmp += y.val[C][R][len_y][top_x ^ len_x];
	amax(z.val[L][R][len][top_x], tmp);
    }
    return z;
};
const Seg unit = Seg();

struct SegmentTree {
    int n, m;
    vector<Seg> d;

    SegmentTree(int n_=1) : n(n_) {
	if (n < 2) m = 1;
	else m = 2 << __lg(n-1);
	d.assign(m*2, unit);
    }

    template<class T> SegmentTree(const vector<T> &a) : n(a.size()) { // When Seg(T) is defined
	if (n < 2) m = 1;
	else m = 2 << __lg(n-1);
	d.assign(m*2, unit);
	REP (i, n) d[i+m] = Seg(a[i]);
	for (int i=m; --i; ) d[i] = d[i*2] * d[i*2+1];
    }

    void modify(int x, const Seg &s) {
	x += m;
	d[x] = s;
	for (x>>=1; x; x>>=1) d[x] = d[x*2] * d[x*2+1];
    }

//    void add(int x, int y, LL v) { add(x, y, v, 1, 0, m); }
//
//    void add(int x, int y, LL v, int k, int l, int r) {
//	if (r<=x || y<=l) return;
//	if (x<=l && r<=y) { d[k] += v; return; } // TODO: Seg update
//	add(x, y, v, k*2, l, (l+r)/2); add(x, y, v, k*2+1, (l+r)/2, r); 
//	d[k] = d[k*2] * d[k*2+1];
//    }

    Seg query(int x, int y) { return query(x, y, 1, 0, m); }

    Seg query(int x, int y, int k, int l, int r) {
	if (r<=x || y<=l) return unit;
	if (x<=l && r<=y) return d[k];
	return query(x, y, k*2, l, (l+r)/2) * query(x, y, k*2+1, (l+r)/2, r);
    }
};



int N, Q;
int A[50111];
LL dp[50011][2][2][2];

int main() {
    scanf("%d", &N);
    REP (i, N) scanf("%d", A+i);

    VI A_(N+2);
    REP (i, N) A_[i+1] = A[i];
    SegmentTree X(A_);

    scanf("%d", &Q);
    REP ($, Q) {
	int k, x;
	scanf("%d%d", &k, &x);;
	X.modify(k, x);
	Seg s = X.query(1, N+1);
	LL ans = 0;
	REP (L, 2) REP (R, 2) REP (l, 2) {
	    amax(ans, s.val[L*2][R|2][l][L]);
	}
	printf("%lld\n", ans);

    }



    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:118:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
./Main.cpp:119:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     REP (i, N) scanf("%d", A+i);
                                ^
./Main.cpp:125:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
                    ^
./Main.cpp:128:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &k, &x);;
                       ^

Judge Result