oj.uz

답안 #468938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
468938 2021-08-30T08:59:31 Z sinamhdv ZIGZAG (INOI20_zigzag) C++11
43 / 100
 2000 ms 13544 KB 
#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 = 100100;

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

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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1100 KB Output is correct
2 Correct 11 ms 1132 KB Output is correct
3 Correct 11 ms 1100 KB Output is correct
4 Correct 11 ms 1136 KB Output is correct
5 Correct 10 ms 1136 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 7 ms 972 KB Output is correct

Subtask #2
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2068 ms 4936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1100 KB Output is correct
2 Correct 11 ms 1132 KB Output is correct
3 Correct 11 ms 1100 KB Output is correct
4 Correct 11 ms 1136 KB Output is correct
5 Correct 10 ms 1136 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 7 ms 972 KB Output is correct
8 Correct 340 ms 13544 KB Output is correct
9 Correct 338 ms 13380 KB Output is correct
10 Correct 360 ms 13480 KB Output is correct
11 Correct 170 ms 11256 KB Output is correct
12 Correct 361 ms 13524 KB Output is correct
13 Correct 345 ms 13432 KB Output is correct
14 Correct 307 ms 13408 KB Output is correct
15 Correct 340 ms 13536 KB Output is correct
16 Correct 328 ms 13388 KB Output is correct
17 Correct 309 ms 13412 KB Output is correct
18 Correct 147 ms 13156 KB Output is correct
19 Correct 150 ms 13256 KB Output is correct

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1100 KB Output is correct
2 Correct 11 ms 1132 KB Output is correct
3 Correct 11 ms 1100 KB Output is correct
4 Correct 11 ms 1136 KB Output is correct
5 Correct 10 ms 1136 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 7 ms 972 KB Output is correct
8 Execution timed out 2068 ms 4936 KB Time limit exceeded
9 Halted 0 ms 0 KB -