제출 #623630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
623630		Arinoor	ZIGZAG (INOI20_zigzag)	C++17	0 / 100	845 ms	84296 KiB

Main

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

#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define mid				((l + r) >> 1)
#define lc				(id << 1)
#define rc				(lc | 1)
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'
#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 3e5 + 10;
const int mod = 1e9 + 7;
const int inf = 1e9 + 10;

struct node{
	ll ans;
	int L, R;
	ll l1, l2, r1, r2;
	int len;
};

node operator + (node l, node r){
	if(l.ans == -1) return r;
	if(r.ans == -1) return l;
	node S;
	S.len = l.len + r.len;
	S.l1 = l.l1, S.r1 = r.r1;
	if(l.len > 1)
		S.l2 = l.l2;
	else
		S.l2 = r.l1;
	if(r.len > 1)
		S.r2 = r.r2;
	else
		S.r2 = l.r1;
	S.L = l.L;
	if(l.L == l.len){
		if(l.r1 != r.l1 and (l.len == 1 or (l.r2 < l.r1) != (l.r1 < r.l1))){
			S.L ++;
			if(r.len == 1 or (l.r1 < r.l1) != (r.l1 < r.l2)){
				S.L = l.L + r.L;
			}
		}
	}
	S.R = r.R;
	if(r.R == r.len){
		if(r.l1 != l.r1 and (r.len == 1 or (l.r1 < r.l1) != (r.l1 < r.l2))){
			S.R ++;
			if(l.len == 1 or (l.r2 < l.r1) != (l.r1 < r.l1)){
				S.R = r.R + l.R;
			}
		}
	}
	S.ans = l.ans + r.ans;
	if(l.r1 != r.l1){
		int valL = 1, valR = 1;
		if(r.len == 1 or (l.r1 < r.l1) != (r.l1 < r.l2))
			valR = r.L;
		if(l.len == 1 or (l.r2 < l.r1) != (l.r1 < r.l1))
			valL = l.R;
		S.ans += 1ll * valL * valR;
	}
	return S;
}

int a[maxn];
pair<int, ll> lz[maxn << 2];
node seg[maxn << 2];

void build(int id, int l, int r){
	seg[id].ans = seg[id].len = r - l;
	seg[id].L = seg[id].R = 1;
	lz[id] = mp(1, 0);
	if(l + 1 == r)
		return;
	build(lc, l, mid);
	build(rc, mid, r);
}

void shift(int id, int l, int r);

void update(int id, int l, int r, int ql, int qr, bool t, int x){
	if(qr <= l or r <= ql)
		return;
	if(l >= ql and r <= qr){
		if(t){
			seg[id].l1 *= -1;
			seg[id].r1 *= -1;
			if(seg[id].len > 1){
				seg[id].l2 *= -1;
				seg[id].r2 *= -1;
			}
			lz[id].fi *= -1;
			lz[id].se *= -1;
		}
		else{
			seg[id].l1 += x;
			seg[id].r1 += x;
			if(seg[id].len > 1){
				seg[id].l2 += x;
				seg[id].r2 += x;
			}
			lz[id].se += x;
		}
		return;
	}
	shift(id, l, r);
	update(lc, l, mid, ql, qr, t, x);
	update(rc, mid, r, ql, qr, t, x);
	seg[id] = seg[lc] + seg[rc];
}

void shift(int id, int l, int r){
	if(lz[id].fi == -1){
		update(lc, l, mid, l, mid, 1, -1);
		update(rc, mid, r, mid, r, 1, -1);
		lz[id].fi = 1;
	}
	if(lz[id].se){
		update(lc, l, mid, l, mid, 0, lz[id].se);
		update(rc, mid, r, mid, r, 0, lz[id].se);
		lz[id].se = 0;
	}
}

node get(int id, int l, int r, int ql, int qr){
	if(qr <= l or r <= ql)
		return node{-1, -1, -1, -1, -1, -1, -1};
	if(l >= ql and r <= qr)
		return seg[id];
	shift(id, l, r);
	node L = get(lc, l, mid, ql, qr);
	node R = get(rc, mid, r, ql, qr);
	if(id == -1){
		bug(L.ans), bug(L.L), bug(L.R), bug(L.l1), bug(L.l2), bug(L.r1), bug(L.r2), bug(L.len);
		bug(R.ans), bug(R.L), bug(R.R), bug(R.l1), bug(R.l2), bug(R.r1), bug(R.r2), bug(R.len);
	}
	return L + R;
}

int main(){
	ios;
	int n, q;
	cin >> n >> q;
	build(1, 0, n);
	for(int i = 0; i < n; i ++){
		cin >> a[i];
		update(1, 0, n, i, i + 1, 0, a[i]);
	}
	while(q--){
		char c;
		int l, r;
		cin >> c >> l >> r;
		l --;
		if(c == '+'){
			int x; cin >> x;
			update(1, 0, n, l, r, 0, x);
		}
		if(c == '*'){
			update(1, 0, n, l, r, 1, -1);
		}
		if(c == '?'){
			cout << get(1, 0, n, l, r).ans << '\n';
		}
	}
}

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