| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1003557 |
2024-06-20T12:58:07 Z |
vjudge1 |
ZIGZAG (INOI20_zigzag) |
C++17 |
|
781 ms |
104564 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3F3F3F3F3F3F3F3F
const int MXN = 3e5 + 5;
const int LOG = 20;
const int mod = 1e9 + 7;
struct SegTree
{
int n;
vector<int> st;
vector<array<int, 2>> lz;
void init(int N)
{
n = N;
st.assign((n + 5) << 2, 0);
lz.assign((n + 5) << 2, {0, 0});
}
void relax(int l, int r, int x)
{
if (!lz[x][0] && !lz[x][1]) return;
if (lz[x][0])
{
st[x] *= -1;
}
st[x] += lz[x][1];
if (l == r)
{
lz[x] = {0, 0};
return;
}
if (lz[x][0]) lz[2*x][1] *= -1, lz[2*x + 1][1] *= -1, lz[2*x][0] ^= 1, lz[2*x + 1][0] ^= 1;
lz[2*x][1] += lz[x][1], lz[2*x + 1][1] += lz[x][1];
lz[x] = {0, 0};
}
void add(int l, int r, int x, int lx, int rx, int val)
{
relax(l, r, x);
if (l > rx || r < lx) return;
if (l >= lx && r <= rx)
{
if (val == inf)
{
lz[x][1] *= -1;
lz[x][0] ^= 1;
}
else
{
lz[x][1] += val;
}
relax(l, r, x);
// cout << l << ' ' << r << ' ' << st[x] << '\n';
return;
}
int mid = (l + r) >> 1;
add(l, mid, 2*x, lx, rx, val);
add(mid + 1, r, 2*x + 1, lx, rx, val);
}
int get(int l, int r, int x, int lx, int rx)
{
relax(l, r, x);
if (l > rx || r < lx) return 0;
if (l >= lx && r <= rx) return st[x];
int mid = (l + r) >> 1;
return get(l, mid, 2*x, lx, rx) + get(mid + 1, r, 2*x + 1, lx, rx);
// cout << l << ' ' << r << ' ' << st[x].ans << ' ' << brute(l, r) << ' ' << st[x].p0 << ' ' << st[x].p1 << ' ' << st[x].s0 << ' ' << st[x].s1 << ' ' << st[x].t << ' ' << st[x].L << ' ' << st[x].R << '\n';
}
};
struct DATA
{
int p0 = 0, p1 = 0, s0 = 0, s1 = 0, ans = 0, l = 0, r = 0;
};
int n;
DATA st[MXN << 2];
int lz[MXN << 2];
int a[MXN], val[MXN];
DATA combine(DATA a, DATA b)
{
if (a.p0 == -1) return b;
if (b.p0 == -1) return a;
int sza = a.r - a.l + 1, szb = b.r - b.l + 1;
DATA res;
res.ans = a.ans + b.ans;
res.ans += a.s1 * b.p0;
res.ans += a.s0 * b.p1;
res.p0 = a.p0, res.p1 = a.p1;
res.s0 = b.s0, res.s1 = b.s1;
if (a.p0 == sza)
{
if ((sza & 1)) res.p0 += b.p1;
else res.p0 += b.p0;
}
if (a.p1 == sza)
{
if ((sza & 1)) res.p1 += b.p0;
else res.p1 += b.p1;
}
if (b.s0 == szb)
{
if ((szb & 1)) res.s0 += a.s1;
else res.s0 += a.s0;
}
if (b.s1 == szb)
{
if ((szb & 1)) res.s1 += a.s0;
else res.s1 += a.s1;
}
res.l = a.l, res.r = b.r;
return res;
}
void build(int l, int r, int x)
{
if (l == r)
{
st[x] = {(val[l] == 0), (val[l] == 1), (val[l] == 0), (val[l] == 1), (val[l] != 2), l, l};
// cout << l << ' ' << r << ' ' << st[x].p0 << ' ' << st[x].p1 << ' ' << st[x].s0 << ' ' << st[x].s1 << ' ' << st[x].ans << '\n';
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*x), build(mid + 1, r, 2*x + 1);
st[x] = combine(st[2*x], st[2*x + 1]);
// cout << l << ' ' << r << ' ' << st[x].p0 << ' ' << st[x].p1 << ' ' << st[x].s0 << ' ' << st[x].s1 << ' ' << st[x].ans << '\n';
}
void relax(int l, int r, int x)
{
if (!lz[x]) return;
swap(st[x].p0, st[x].p1);
swap(st[x].s0, st[x].s1);
lz[x] = 0;
if (l == r) return;
lz[2*x] ^= 1, lz[2*x + 1] ^= 1;
}
void upd(int l, int r, int x, int lx, int rx)
{
relax(l, r, x);
if (l > rx || r < lx) return;
if (l >= lx && r <= rx)
{
lz[x] ^= 1;
relax(l, r, x);
return;
}
int mid = (l + r) >> 1;
upd(l, mid, 2*x, lx, rx);
upd(mid + 1, r, 2*x + 1, lx, rx);
st[x] = combine(st[2*x], st[2*x + 1]);
}
void make(int l, int r, int x, int lx, int rx)
{
relax(l, r, x);
if (l > rx || r < lx) return;
if (l >= lx && r <= rx)
{
st[x] = {(val[l] == 0), (val[l] == 1), (val[l] == 0), (val[l] == 1), (val[l] != 2), l, l};
return;
}
int mid = (l + r) >> 1;
make(l, mid, 2*x, lx, rx);
make(mid + 1, r, 2*x + 1, lx, rx);
st[x] = combine(st[2*x], st[2*x + 1]);
}
DATA get(int l, int r, int x, int lx, int rx)
{
if (l > rx || r < lx) return {-1, 0, 0, 0, 0, 0, 0};
relax(l, r, x);
if (l >= lx && r <= rx) return st[x];
int mid = (l + r) >> 1;
return combine(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int q;
cin >> n >> q;
SegTree st1;
st1.init(n);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
st1.add(1, n, 1, i, i, a[i]);
}
for (int i = 1; i < n; i++)
{
if (a[i] < a[i + 1]) val[i] = 0;
else if (a[i] > a[i + 1]) val[i] = 1;
else val[i] = 2;
}
build(1, n - 1, 1);
while (q--)
{
char ch;
cin >> ch;
if (ch == '?')
{
int l, r;
cin >> l >> r;
cout << get(1, n - 1, 1, l, r - 1).ans + (r - l + 1) << '\n';
}
else if (ch == '+')
{
int l, r, v;
cin >> l >> r >> v;
st1.add(1, n, 1, l, r, v);
if (l > 1)
{
int x = st1.get(1, n, 1, l - 1, l - 1);
int y = st1.get(1, n, 1, l, l);
if (x < y) val[l - 1] = 0;
else if (x > y) val[l - 1] = 1;
else val[l - 1] = 2;
make(1, n - 1, 1, l - 1, l - 1);
}
if (r < n)
{
int x = st1.get(1, n, 1, r, r);
int y = st1.get(1, n, 1, r + 1, r + 1);
if (x < y) val[r] = 0;
else if (x > y) val[r] = 1;
else val[r] = 2;
make(1, n - 1, 1, r, r);
}
}
else if (ch == '*')
{
int l, r;
cin >> l >> r;
st1.add(1, n, 1, l, r, inf);
upd(1, n - 1, 1, l, r - 1);
if (r < n)
{
int x = st1.get(1, n, 1, r, r);
int y = st1.get(1, n, 1, r + 1, r + 1);
if (x < y) val[r] = 0;
else if (x > y) val[r] = 1;
else val[r] = 2;
make(1, n - 1, 1, r, r);
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
2160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
781 ms |
104564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
2160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
2160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
