Submission #635397

#	Time	Username	Problem	Language	Result	Execution time	Memory
635397		NothingXD	ZIGZAG (INOI20_zigzag)	C++17	100 / 100	928 ms	63164 KiB

Main

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int maxn = 3e5 + 10;

struct Seg{
	ll ans, x, y;
	int l, r, sz;
	Seg(){};
	Seg(ll x, ll y, int l, int r, int sz, ll ans){
		this->l = l;
		this->r = r;
		this->x = x;
		this->y = y;
		this->sz = sz;
		this->ans = ans;
	}
};

Seg operator +(Seg a, Seg b){
	Seg res;
	if (a.sz == 0) return b;
	if (b.sz == 0) return a;
	res.ans = a.ans + b.ans;
	res.sz = a.sz + b.sz;
	res.x = a.x;
	res.y = b.y;
	res.l = a.l;
	res.r = b.r;
	if (a.y > b.x){
		res.ans += 1ll * (max(0, -a.r) + 1) * (max(0, b.l) + 1);
		if (a.l == 0 && a.sz == 1){
			res.l = -max(b.l, 0) - 1;
		}
		else if (abs(a.l) == -a.r && abs(a.l) == a.sz - 1){
			if (a.l < 0) res.l = a.l - max(0, b.l) - 1;
			else res.l = a.l + max(0, b.l) + 1;
		}
		if (b.r == 0 && b.sz == 1){
			res.r = max(-a.r, 0) + 1;
		}
		else if (b.l == abs(b.r) && abs(b.r) == b.sz - 1){
			if (b.r < 0) res.r = b.r - max(0, -a.r) - 1;
			else res.r = b.r + max(0, -a.r) + 1;
		}
	}
	else if (a.y < b.x){
		res.ans += 1ll * (max(0, a.r) + 1) * (max(0, -b.l) + 1);
		if (a.l == 0 && a.sz == 1){
			res.l = max(-b.l, 0) + 1;
		}
		else if (abs(a.l) == a.r && abs(a.l) == a.sz - 1){
			if (a.l < 0) res.l = a.l - max(0, -b.l) - 1;
			else res.l = a.l + max(0, -b.l) + 1;
		}
		if (b.r == 0 && b.sz == 1){
			res.r = -max(a.r, 0) - 1;
		}
		else if (-b.l == abs(b.r) && abs(b.r) == b.sz - 1){
			if (b.r < 0) res.r = b.r - max(0, a.r) - 1;
			else res.r = b.r + max(0, a.r) + 1;
		}
	}
	return res;
}

int n, q, a[maxn];
pll lazy[maxn << 2];
Seg seg[maxn << 2];

void build(int v, int l, int r){
	if (l + 1 == r){
		seg[v] = Seg(a[l], a[l], 0, 0, 1, 1);
		return;
	}
	int mid = (l + r) >> 1;
	build(v << 1, l, mid);
	build(v << 1 | 1, mid, r);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
//	debug(l, r, seg[v].x, seg[v].y, seg[v].l, seg[v].r, seg[v].sz, seg[v].ans);
}

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

void add(int v, int l, int r, int ql, int qr, ll val){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		seg[v].x += val;
		seg[v].y += val;
		lazy[v].F += val;
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	add(v << 1, l, mid, ql, qr, val);
	add(v << 1 | 1, mid, r, ql, qr, val);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

void reverse(int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		seg[v].x = -seg[v].x;
		seg[v].y = -seg[v].y;
		seg[v].l = -seg[v].l;
		seg[v].r = -seg[v].r;
		lazy[v].S++;
		lazy[v].F = -lazy[v].F;
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	reverse(v << 1, l, mid, ql, qr);
	reverse(v << 1 | 1, mid, r, ql, qr);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

Seg get(int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return Seg(0, 0, 0, 0, 0, 0);
	if (ql <= l && r <= qr) return seg[v];
	shift(v, l, r);
	int mid = (l + r) >> 1;
	return get(v << 1, l, mid, ql, qr)
		+ get(v << 1 | 1, mid, r, ql, qr);
}

void shift(int v, int l, int r){
	if (lazy[v].S & 1){
		int mid = (l + r) >> 1;
		reverse(v << 1, l, mid, l, mid);
		reverse(v << 1 | 1, mid, r, mid, r);
		lazy[v].S = 0;
	}
	if (lazy[v].F == 0) return;
	int mid = (l + r) >> 1;
	add(v << 1, l, mid, l, mid, lazy[v].F);
	add(v << 1 | 1, mid, r, mid, r, lazy[v].F);
	lazy[v].F = 0;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n >> q;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}

	build(1, 1, n+1);

	while(q--){
		char t; int l, r; cin >> t >> l >> r;
		if (t == '*') reverse(1, 1, n+1, l, r+1);
		else if (t == '+'){
			int x; cin >> x;
			add(1, 1, n+1, l, r+1, x);
		}
		else{
			cout << get(1, 1, n+1, l, r+1).ans << '\n';
		}
	}

	return 0;
}

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