| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 795723 |
2023-07-27T13:32:32 Z |
MISM06 |
ZIGZAG (INOI20_zigzag) |
C++17 |
|
845 ms |
123368 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair < int , int > pii;
typedef pair < int , pii > piii;
typedef pair < ll , ll > pll;
typedef pair < ll , pll > plll;
#define pb push_back
#define all(x) x.begin(), x.end()
#define sze size()
#define F first
#define S second
#define kids int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1;
#define wall__ cout << "________________________________________\n";
const ll N = 3e5 + 10, mod = 1e9 + 7;
struct node {
ll ans, vl, vr, pre[2], suf[2], is[2], t, len;
node () {
ans = 0; vl = 0; vr = 0; pre[0] = pre[1] = 0; suf[0] = suf[1] = 0; is[0] = is[1] = 0; t = 1;
len = 0;
}
void set_len (int x) {
len = x; t = len % 2; t ^= 1;
}
void merge (node x, node y) {
len = x.len + y.len;
set_len(len);
vl = x.vl; vr = y.vr;
ans = x.ans + y.ans;
if (x.vr < y.vl) ans += x.suf[0] * y.pre[0];
if (x.vr > y.vl) ans += x.suf[1] * y.pre[1];
pre[0] = x.pre[0];
pre[1] = x.pre[1];
suf[0] = y.suf[0];
suf[1] = y.suf[1];
if (x.vr > y.vl) {
if (x.t == 0) pre[0] += y.pre[1] * x.is[0];
if (x.t == 1) pre[1] += y.pre[1] * x.is[1];
if (y.t == 0) suf[0] += y.is[0] * x.suf[1];
if (y.t == 1) suf[1] += y.is[1] * x.suf[1];
} else if (x.vr < y.vl) {
if (x.t == 1) pre[0] += y.pre[0] * x.is[0];
if (x.t == 0) pre[1] += y.pre[0] * x.is[1];
if (y.t == 1) suf[0] += y.is[0] * x.suf[1];
if (y.t == 0) suf[1] += y.is[1] * x.suf[1];
}
is[0] = is[1] = 0;
if (x.vr > y.vl) {
is[x.t] = x.is[x.t] & y.is[1];
} else if (x.vr < y.vl) {
is[x.t ^ 1] = x.is[x.t ^ 1] & y.is[0];
}
}
void relax (ll x, ll y) {
if (x == -1) {
swap(pre[0], pre[1]);
swap(suf[0], suf[1]);
vl *= -1ll;
vr *= -1ll;
swap(is[0], is[1]);
}
vl += y;
vr += y;
}
void make (ll x) {
set_len(1);
vl = x; vr = x;
pre[0] = pre[1] = 1;
suf[0] = suf[1] = 1;
ans = 1;
is[0] = is[1] = 1;
}
};
int n, a[N];
struct segtree {
node seg[N << 2];
ll la1[N << 2], la2[N << 2];
void build (int v = 1, int tl = 1, int tr = n) {
la1[v] = 1; la2[v] = 0;
if (tl == tr) {
seg[v].make(a[tl]);
return;
} kids;
build(cl, tl, mid);
build(cr, mid + 1, tr);
seg[v].merge(seg[cl], seg[cr]);
}
void shift (int v, int tl, int tr) {
seg[v].relax(la1[v], la2[v]);
int cl = v << 1, cr = v << 1 | 1;
if (tl != tr) {
la1[cl] *= la1[v];
la2[cl] *= la1[v];
la2[cl] += la2[v];
la1[cr] *= la1[v];
la2[cr] *= la1[v];
la2[cr] += la2[v];
}
la1[v] = 1;
la2[v] = 0;
}
void upd (int s, ll val, int l, int r, int v = 1, int tl = 1, int tr = n) {
shift(v, tl, tr);
if (l > r) return;
if (l == tl && r == tr) {
if (s == 0) la2[v] += val;
else la1[v] *= -1ll;
shift(v, tl, tr);
return;
} kids
upd(s, val, l, min(r, mid), cl, tl, mid);
upd(s, val, max(l, mid + 1), r, cr , mid + 1, tr);
seg[v].merge(seg[cl], seg[cr]);
}
node ask (int l, int r, int v = 1, int tl = 1, int tr = n) {
shift(v, tl, tr);
if (l == tl && r == tr) return seg[v];
kids
if (r <= mid) return ask(l, r, cl, tl, mid);
else if (l > mid) return ask(l, r, cr, mid + 1, tr);
else {
node res;
res.merge(ask(l, mid, cl, tl, mid), ask(mid + 1, r, cr, mid + 1, tr));
return res;
}
}
} f;
void solve () {
int q; cin >> n >> q;
for (int i =1 ; i <= n; i++) cin >> a[i];
f.build();
while(q--) {
char t; cin >> t; int l, r; cin >> l >> r;
if (t == '?') {
cout << f.ask(l, r).ans << '\n';
} else if (t == '+') {
ll x; cin >> x;
f.upd(0, x, l, r);
} else {
f.upd(1, 0, l, r);
}
}
}
int main() {
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
return 0;
}
/*
3 1
1 1 1
? 2 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
103984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
845 ms |
123368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
103984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
103984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
