| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1003332 |
2024-06-20T09:00:56 Z |
vjudge1 |
ZIGZAG (INOI20_zigzag) |
C++17 |
|
2000 ms |
84684 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 DATA
{
int p0 = 0, p1 = 0, s0 = 0, s1 = 0, L = 0, R = 0, ans = 0, t = 0, l = 0, r = 0;
};
struct LDATA
{
int sw = 0, L = 0, R = 0;
};
int n;
DATA st[MXN << 2];
LDATA lz[MXN << 2];
int a[MXN];
int brute(int s, int e)
{
int res = e - s + 1;
for (int i = s; i + 1 <= e; i++)
{
int f = 1;
if (a[i] < a[i + 1])
{
for (int j = i + 1; j <= e; j++)
{
if ((j - i) & 1)
{
f &= (a[j - 1] < a[j]);
}
else
{
f &= (a[j - 1] > a[j]);
}
res += f;
}
}
else
{
for (int j = i + 1; j <= e; j++)
{
if ((j - i) & 1)
{
f &= (a[j - 1] > a[j]);
}
else
{
f &= (a[j - 1] < a[j]);
}
res += f;
}
}
}
return res;
}
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;
if (a.R < b.L) res.ans += a.s0 * b.p0;
if (a.R > b.L) res.ans += a.s1 * b.p1;
res.p0 = a.p0, res.p1 = a.p1;
res.s0 = b.s0, res.s1 = b.s1;
res.t = 3;
if (a.t == 0 || a.t == 2)
{
if ((sza & 1) && a.R > b.L) res.p0 += b.p1;
else if (!(sza & 1) && a.R < b.L) res.p0 += b.p0;
}
if (a.t == 1 || a.t == 2)
{
if ((sza & 1) && a.R < b.L) res.p1 += b.p0;
else if (!(sza & 1) && a.R > b.L) res.p1 += b.p1;
}
if (b.t == 0 || b.t == 2)
{
if ((szb & 1) && a.R < b.L) res.s1 += a.s0;
else if (!(szb & 1) && a.R < b.L) res.s0 += a.s0;
}
if (b.t == 1 || b.t == 2)
{
if ((szb & 1) && a.R > b.L) res.s0 += a.s1;
else if (!(szb & 1) && a.R > b.L) res.s1 += a.s1;
}
if (a.t == 3 || b.t == 3) res.t = 3;
else
{
if (a.t == 2 && b.t == 2)
{
if (a.R < b.L) res.t = 1;
else if (a.R > b.L) res.t = 0;
}
if (a.t == 2 && b.t <= 1)
{
if (a.R < b.L) res.t = 1;
else if (a.R > b.L) res.t = 0;
if (1 - b.t != res.t) res.t = 3;
}
if (a.t == 1 && b.t == 1 && !(sza & 1)) res.t = 1;
if (a.t == 1 && b.t == 0 && (sza & 1)) res.t = 1;
if (a.t == 0 && b.t == 1 && (sza & 1)) res.t = 0;
if (a.t == 0 && b.t == 0 && !(sza & 1)) res.t = 0;
}
res.L = a.L, res.R = b.R;
res.l = a.l, res.r = b.r;
return res;
}
void build(int l, int r, int x)
{
if (l == r)
{
st[x] = {1, 1, 1, 1, a[l], a[l], 1, 2, l, l};
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]);
}
void relax(int l, int r, int x)
{
if (!lz[x].sw && !lz[x].L && !lz[x].R) return;
if (lz[x].sw)
{
st[x].L *= -1, st[x].R *= -1;
swap(st[x].p0, st[x].p1);
swap(st[x].s0, st[x].s1);
if (st[x].t <= 1) st[x].t ^= 1;
}
st[x].L += lz[x].L, st[x].R += lz[x].R;
if (l == r)
{
lz[x] = {0, 0, 0};
return;
}
lz[2*x].sw ^= lz[x].sw, lz[2*x + 1].sw ^= lz[x].sw;
lz[2*x].L += lz[x].L, lz[2*x + 1].L += lz[x].L;
lz[2*x].R += lz[x].R, lz[2*x + 1].R += lz[x].R;
lz[x] = {0, 0, 0};
}
void upd(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].sw ^= 1;
lz[x].L *= -1;
lz[x].R *= -1;
}
else
{
lz[x].L += val, lz[x].R += val;
}
relax(l, r, x);
// 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';
return;
}
int mid = (l + r) >> 1;
upd(l, mid, 2*x, lx, rx, val);
upd(mid + 1, r, 2*x + 1, lx, rx, val);
st[x] = combine(st[2*x], st[2*x + 1]);
// 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';
}
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, 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;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, n, 1);
while (q--)
{
char ch;
cin >> ch;
if (ch == '?')
{
int l, r;
cin >> l >> r;
// cout << get(1, n, 1, l, r).ans << '\n';
cout << brute(l, r) << '\n';
}
else if (ch == '+')
{
int l, r, v;
cin >> l >> r >> v;
for (int i = l; i <= r; i++) a[i] += v;
// upd(1, n, 1, l, r, v);
// cout << '\n';
}
else if (ch == '*')
{
int l, r;
cin >> l >> r;
for (int i = l; i <= r; i++) a[i] *= -1;
// upd(1, n, 1, l, r, inf);
// cout << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2059 ms |
1788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2087 ms |
84684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2059 ms |
1788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2059 ms |
1788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
