Submission #468940

#	Time	Username	Problem	Language	Result	Execution time	Memory
468940		sinamhdv	ZIGZAG (INOI20_zigzag)	C++11	100 / 100	1313 ms	60976 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;

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

#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];
	ll lz[4 * MAXN];
	bool neglz[4 * MAXN];
	inline void build(int v = 1, int l = 0, int r = n - 1)
	{
		if (l == r)
		{
			seg[v] = a[l];
			return;
		}
		int mid = (r + l) / 2;
		build(2 * v, l, mid);
		build(2 * v + 1, mid + 1, r);
		seg[v] = min(seg[2 * v], seg[2 * v + 1]);
	}

	inline void pushdown(int v)
	{
		if (neglz[v])
		{
			FOR(t, 2 * v , 2 * v + 2)
			{
				neglz[t] ^= 1;
				lz[t] *= -1;
				seg[t] *= -1;
			}
			neglz[v] = 0;
		}
		if (lz[v])
		{
			FOR(t, 2* v, 2* v + 2)
			{
				seg[t] += lz[v];
				lz[t] += lz[v];
			}
			lz[v] = 0;
		}
	}

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

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

	inline ll getind(int i, int v = 1, int l = 0, int r = n - 1)
	{
		if (l == r) return seg[v];
		int mid = (r + l) / 2;
		pushdown(v);
		if (i <= mid) return getind(i,2 * v, l, mid);
		else return getind(i, 2 * v + 1, mid + 1, r);
	}
} addseg;

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

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;
	scanf("%d %d", &n, &q);

	FOR(i, 0, n) scanf("%d", a + i);

	if (n == 1)
	{
		while (q--)
		{
			char op; int l, r , x;
			scanf(" %c %d %d", &op, &l, &r);
			if (op == '+') scanf("%d", &x);
			if (op == '?') putchar('1'), putchar('\n');
		}
		return 0;
	}

	addseg.build();
	build();

	while (q--)
	{
		char op;
		int l, r;
		scanf(" %c %d %d ", &op, &l, &r);
		l--; r--;
		if (op == '+')
		{
			int x;
			scanf("%d", &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);
			printf("%lld\n", res.val + (r - l + 1));
		}
	}

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:234:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  234 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:236:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  236 |  FOR(i, 0, n) scanf("%d", a + i);
      |               ~~~~~^~~~~~~~~~~~~
Main.cpp:243:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  243 |    scanf(" %c %d %d", &op, &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:244:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  244 |    if (op == '+') scanf("%d", &x);
      |                   ~~~~~^~~~~~~~~~
Main.cpp:257:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  257 |   scanf(" %c %d %d ", &op, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:262:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  262 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~

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