Submission #468891

#	Time	Username	Problem	Language	Result	Execution time	Memory
468891		sinamhdv	ZIGZAG (INOI20_zigzag)	C++11	0 / 100	2084 ms	1048580 KiB

Main

#include <bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int MAXN = 300100;

int n, q;
int a[MAXN];

inline int getsgn(ll x, ll y)
{
	if (x == y) return 0;
	return (x < y ? 1 : 2);
}

struct ADDSEG
{
	ll seg[4 * MAXN];
	inline void build(void)
	{
		FOR(i, 0, n) seg[i] = a[i];
	}

	inline void add(int L, int R, int x)
	{
		FOR(i, L, R + 1) seg[i] += x;
	}

	inline void neg(int L, int R)
	{
		FOR(i, L, R + 1) seg[i] = -seg[i];
	}

	inline ll getind(int i)
	{
		return seg[i];
	}
} addseg;

struct node
{
	int al, ar;
	ll val;
	int pref, suf;
	bool lz;
	int len;
};

inline void dbgnode(node &v)
{
	dbg(v.al);
	dbg(v.ar);
	dbg(v.val);
	dbg(v.pref);
	dbg(v.suf);
	dbg(v.lz);
	dbg(v.len);
	dbg("============\n");
}

node seg[4 * MAXN];

inline void pushdown(int v)
{
	if (!seg[v].lz) return;
	FOR(t, 2 * v, 2 * v + 2)
	{
		seg[t].lz ^= 1;
		if (seg[t].al) seg[t].al = 3 - seg[t].al;
		if (seg[t].ar) seg[t].ar = 3 - seg[t].ar;
	}
	seg[v].lz = 0;
}

inline node mrg(const node &lc, const node &rc)
{
	if (lc.al == -1) return rc;
	if (rc.al == -1) return lc;
	node res = {};
	res.al = lc.al;
	res.ar = rc.ar;
	res.len = lc.len + rc.len;
	if (lc.ar && rc.al && lc.ar != rc.al)	// can join
	{
		res.val = rc.val + lc.val + (ll)lc.suf * rc.pref;
		res.pref = (lc.pref == lc.len ? rc.pref + lc.pref : lc.pref);
		res.suf = (rc.suf == rc.len ? rc.suf + lc.suf : rc.suf);
	}
	else	// no join
	{
		res.val = lc.val + rc.val;
		res.pref = lc.pref;
		res.suf = rc.suf;
	}

	return res;
}

void build(int v = 1, int l = 0, int r = n - 2)
{
	if (l == r)
	{
		int x = getsgn(a[l], a[l + 1]);
		seg[v].al = seg[v].ar = x;
		seg[v].val = seg[v].pref = seg[v].suf = (x != 0);
		seg[v].len = 1;
		// lz not set
		return;
	}
	int mid = (r + l) / 2;
	build(2 * v, l, mid);
	build(2 * v + 1, mid + 1, r);
	seg[v] = mrg(seg[2 * v], seg[2 * v + 1]);
}

inline void tgl(int L, int R, int v = 1, int l = 0, int r = n - 2)
{
	if (l > R || r < L) return;
	if (l >= L && r <= R)
	{
		seg[v].lz ^= 1;
		if (seg[v].al) seg[v].al = 3 - seg[v].al;
		if (seg[v].ar) seg[v].ar = 3 - seg[v].ar;
		return;
	}
	int mid = (r + l) / 2;
	pushdown(v);
	tgl(L, R, 2 * v, l, mid);
	tgl(L, R, 2 * v + 1, mid + 1, r);
	seg[v] = mrg(seg[2 * v], seg[2 * v+  1]);
}

inline node get(int L, int R, int v = 1, int l = 0, int r = n - 2)
{
	if (l > R || r < L) return {-1, -1, 0, 0, 0, 0, 0};
	if (l >= L && r <= R) return seg[v];
	int mid = (r + l) / 2;
	pushdown(v);
	return mrg(get(L, R, 2 * v, l, mid), get(L, R, 2 * v + 1, mid + 1, r));
}

inline void setind(int i, int v = 1, int l = 0, int r  = n - 2)
{
	if (l == r)
	{
		int x = getsgn(addseg.getind(l), addseg.getind(l + 1));
		seg[v].al = seg[v].ar = x;
		seg[v].val = seg[v].pref = seg[v].suf = (x != 0);
		// lz not set
		return;
	}
	int mid = (r + l) / 2;
	pushdown(v);
	if (i <= mid) setind(i, 2* v, l, mid);
	else setind(i, 2 * v + 1, mid + 1, r);
	seg[v] = mrg(seg[2 * v], seg[2 * v + 1]);
}

int32_t main(void)
{
	fast_io;
	cin >> n >> q;

	FOR(i, 0, n) cin >> a[i];

	addseg.build();
	build();

/*	FOR(v, 1, 6)
	{
		dbg(v);
		dbgnode(seg[v]);
	}*/

	while (q--)
	{
		char op;
		int l, r;
		cin >> op >> l >> r;
		l--; r--;
		if (op == '+')
		{
			int x;
			cin >> x;
			addseg.add(l, r, x);
			if (l > 0) setind(l - 1);
			if (r < n - 1) setind(r);
		}
		else if (op == '*')
		{
			addseg.neg(l, r);
			if (l < r) tgl(l, r - 1);
			if (l > 0) setind(l - 1);
			if (r < n - 1) setind(r);
		}
		else	// ask
		{
			node res = get(l, r - 1);
			cout << res.val + (r - l + 1) << endl;
		}
	}

	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 42
• Subtask 3: 0 / 35
• Subtask 4: 0 / 15