| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 468937 |
2021-08-30T08:50:26 Z |
sinamhdv |
ZIGZAG (INOI20_zigzag) |
C++11 |
|
2000 ms |
16204 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
const int MAXN = 100100;
int n, q;
int a[MAXN];
inline int getsgn(ll x, ll y)
{
if (x == y) return 0;
return (x < y ? 1 : 2);
}
struct ADDSEG
{
ll seg[4 * MAXN];
ll lz[4 * MAXN];
bool neglz[4 * MAXN];
inline void build(int v = 1, int l = 0, int r = n - 1)
{
if (l == r)
{
seg[v] = a[l];
return;
}
int mid = (r + l) / 2;
build(2 * v, l, mid);
build(2 * v + 1, mid + 1, r);
seg[v] = min(seg[2 * v], seg[2 * v + 1]);
}
inline void pushdown(int v)
{
if (neglz[v])
{
FOR(t, 2 * v , 2 * v + 2)
{
neglz[t] ^= 1;
lz[t] *= -1;
seg[t] *= -1;
}
neglz[v] = 0;
}
if (lz[v])
{
FOR(t, 2* v, 2* v + 2)
{
seg[t] += lz[v];
lz[t] += lz[v];
}
lz[v] = 0;
}
}
inline void add(int L, int R, int x, int v = 1, int l = 0, int r = n - 1)
{
if (l > R || r < L) return;
if (l >= L && r <= R)
{
seg[v] += x;
lz[v] += x;
return;
}
int mid = (r + l) / 2;
pushdown(v);
add(L, R, x, 2* v, l, mid);
add(L, R, x, 2 * v + 1, mid + 1, r);
seg[v] = min(seg[2 * v], seg[2 * v + 1]);
}
inline void neg(int L, int R, int v = 1, int l = 0, int r = n - 1)
{
if (l > R || r < L) return;
if (l >= L && r <= R)
{
seg[v] *= -1;
lz[v] *= -1;
neglz[v] ^= 1;
return;
}
int mid = (r + l) / 2;
pushdown(v);
neg(L, R, 2 * v, l, mid);
neg(L, R, 2 * v + 1, mid + 1, r);
seg[v] = min(seg[2 * v], seg[2 * v + 1]);
}
inline ll getind(int i, int v = 1, int l = 0, int r = n - 1)
{
if (l == r) return seg[v];
int mid = (r + l) / 2;
pushdown(v);
if (i <= mid) return getind(i,2 * v, l, mid);
else return getind(i, 2 * v + 1, mid + 1, r);
}
} addseg;
struct node
{
int al, ar;
ll val;
int pref, suf;
bool lz;
int len;
};
/*
inline void dbgnode(node &v)
{
dbg(v.al);
dbg(v.ar);
dbg(v.val);
dbg(v.pref);
dbg(v.suf);
dbg(v.lz);
dbg(v.len);
dbg("============\n");
}
*/
node seg[4 * MAXN];
inline void pushdown(int v)
{
if (!seg[v].lz) return;
FOR(t, 2 * v, 2 * v + 2)
{
seg[t].lz ^= 1;
if (seg[t].al) seg[t].al = 3 - seg[t].al;
if (seg[t].ar) seg[t].ar = 3 - seg[t].ar;
}
seg[v].lz = 0;
}
inline node mrg(const node &lc, const node &rc)
{
if (lc.al == -1) return rc;
if (rc.al == -1) return lc;
node res = {};
res.al = lc.al;
res.ar = rc.ar;
res.len = lc.len + rc.len;
if (lc.ar && rc.al && lc.ar != rc.al) // can join
{
res.val = rc.val + lc.val + (ll)lc.suf * rc.pref;
res.pref = (lc.pref == lc.len ? rc.pref + lc.pref : lc.pref);
res.suf = (rc.suf == rc.len ? rc.suf + lc.suf : rc.suf);
}
else // no join
{
res.val = lc.val + rc.val;
res.pref = lc.pref;
res.suf = rc.suf;
}
return res;
}
void build(int v = 1, int l = 0, int r = n - 2)
{
if (l == r)
{
int x = getsgn(a[l], a[l + 1]);
seg[v].al = seg[v].ar = x;
seg[v].val = seg[v].pref = seg[v].suf = (x != 0);
seg[v].len = 1;
// lz not set
return;
}
int mid = (r + l) / 2;
build(2 * v, l, mid);
build(2 * v + 1, mid + 1, r);
seg[v] = mrg(seg[2 * v], seg[2 * v + 1]);
}
inline void tgl(int L, int R, int v = 1, int l = 0, int r = n - 2)
{
if (l > R || r < L) return;
if (l >= L && r <= R)
{
seg[v].lz ^= 1;
if (seg[v].al) seg[v].al = 3 - seg[v].al;
if (seg[v].ar) seg[v].ar = 3 - seg[v].ar;
return;
}
int mid = (r + l) / 2;
pushdown(v);
tgl(L, R, 2 * v, l, mid);
tgl(L, R, 2 * v + 1, mid + 1, r);
seg[v] = mrg(seg[2 * v], seg[2 * v+ 1]);
}
inline node get(int L, int R, int v = 1, int l = 0, int r = n - 2)
{
if (l > R || r < L) return {-1, -1, 0, 0, 0, 0, 0};
if (l >= L && r <= R) return seg[v];
int mid = (r + l) / 2;
pushdown(v);
return mrg(get(L, R, 2 * v, l, mid), get(L, R, 2 * v + 1, mid + 1, r));
}
inline void setind(int i, int v = 1, int l = 0, int r = n - 2)
{
if (l == r)
{
int x = getsgn(addseg.getind(l), addseg.getind(l + 1));
seg[v].al = seg[v].ar = x;
seg[v].val = seg[v].pref = seg[v].suf = (x != 0);
// lz not set
return;
}
int mid = (r + l) / 2;
pushdown(v);
if (i <= mid) setind(i, 2* v, l, mid);
else setind(i, 2 * v + 1, mid + 1, r);
seg[v] = mrg(seg[2 * v], seg[2 * v + 1]);
}
/*
inline void dbgseg(void)
{
FOR(i, 0, n) cout << addseg.getind(i) << ' ';
cout << endl;
}*/
int32_t main(void)
{
fast_io;
cin >> n >> q;
FOR(i, 0, n) cin >> a[i];
if (n == 1)
{
while (q--)
{
char op; int l, r , x;
cin >> op >> l >> r;
if (op == '+') cin >> x;
if (op == '?') cout << 1 << endl;
}
return 0;
}
addseg.build();
build();
/* FOR(v, 1, 6)
{
dbg(v);
dbgnode(seg[v]);
}*/
/*
dbgseg();
addseg.add(2, 4, 4);
dbgseg();
addseg.neg(0, 5);
dbgseg();
addseg.add(4, 5, -3);
dbgseg();
return 0;
*/
while (q--)
{
char op;
int l, r;
cin >> op >> l >> r;
l--; r--;
if (op == '+')
{
int x;
cin >> x;
addseg.add(l, r, x);
if (l > 0) setind(l - 1);
if (r < n - 1) setind(r);
}
else if (op == '*')
{
addseg.neg(l, r);
if (l < r) tgl(l, r - 1);
if (l > 0) setind(l - 1);
if (r < n - 1) setind(r);
}
else // ask
{
node res = get(l, r - 1);
cout << res.val + (r - l + 1) << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1152 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1156 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1156 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
2 ms |
204 KB |
Output is correct |
| 7 |
Correct |
7 ms |
972 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2064 ms |
640 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1152 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1156 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1156 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
2 ms |
204 KB |
Output is correct |
| 7 |
Correct |
7 ms |
972 KB |
Output is correct |
| 8 |
Correct |
315 ms |
13516 KB |
Output is correct |
| 9 |
Correct |
342 ms |
13532 KB |
Output is correct |
| 10 |
Correct |
323 ms |
13472 KB |
Output is correct |
| 11 |
Correct |
169 ms |
11692 KB |
Output is correct |
| 12 |
Correct |
324 ms |
16196 KB |
Output is correct |
| 13 |
Correct |
332 ms |
16140 KB |
Output is correct |
| 14 |
Correct |
301 ms |
16196 KB |
Output is correct |
| 15 |
Correct |
313 ms |
15116 KB |
Output is correct |
| 16 |
Correct |
327 ms |
16204 KB |
Output is correct |
| 17 |
Correct |
277 ms |
16164 KB |
Output is correct |
| 18 |
Correct |
130 ms |
15596 KB |
Output is correct |
| 19 |
Correct |
132 ms |
15596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
9 ms |
1152 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1156 KB |
Output is correct |
| 4 |
Correct |
10 ms |
1156 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
2 ms |
204 KB |
Output is correct |
| 7 |
Correct |
7 ms |
972 KB |
Output is correct |
| 8 |
Execution timed out |
2064 ms |
640 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
