| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 468938 |
2021-08-30T08:59:31 Z |
sinamhdv |
ZIGZAG (INOI20_zigzag) |
C++11 |
|
2000 ms |
13544 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;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#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;
};
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]);
}
int32_t main(void)
{
// fast_io;
scanf("%d %d", &n, &q);
FOR(i, 0, n) scanf("%d", a + i);
if (n == 1)
{
while (q--)
{
char op; int l, r , x;
scanf(" %c %d %d", &op, &l, &r);
if (op == '+') scanf("%d", &x);
if (op == '?') putchar('1'), putchar('\n');
}
return 0;
}
addseg.build();
build();
while (q--)
{
char op;
int l, r;
scanf(" %c %d %d ", &op, &l, &r);
l--; r--;
if (op == '+')
{
int x;
scanf("%d", &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);
printf("%lld\n", res.val + (r - l + 1));
}
}
return 0;
}
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:234:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
234 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:236:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
236 | FOR(i, 0, n) scanf("%d", a + i);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:243:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
243 | scanf(" %c %d %d", &op, &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:244:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
244 | if (op == '+') scanf("%d", &x);
| ~~~~~^~~~~~~~~~
Main.cpp:257:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
257 | scanf(" %c %d %d ", &op, &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:262:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
262 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
11 ms |
1136 KB |
Output is correct |
| 5 |
Correct |
10 ms |
1136 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 |
2068 ms |
4936 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
11 ms |
1136 KB |
Output is correct |
| 5 |
Correct |
10 ms |
1136 KB |
Output is correct |
| 6 |
Correct |
2 ms |
204 KB |
Output is correct |
| 7 |
Correct |
7 ms |
972 KB |
Output is correct |
| 8 |
Correct |
340 ms |
13544 KB |
Output is correct |
| 9 |
Correct |
338 ms |
13380 KB |
Output is correct |
| 10 |
Correct |
360 ms |
13480 KB |
Output is correct |
| 11 |
Correct |
170 ms |
11256 KB |
Output is correct |
| 12 |
Correct |
361 ms |
13524 KB |
Output is correct |
| 13 |
Correct |
345 ms |
13432 KB |
Output is correct |
| 14 |
Correct |
307 ms |
13408 KB |
Output is correct |
| 15 |
Correct |
340 ms |
13536 KB |
Output is correct |
| 16 |
Correct |
328 ms |
13388 KB |
Output is correct |
| 17 |
Correct |
309 ms |
13412 KB |
Output is correct |
| 18 |
Correct |
147 ms |
13156 KB |
Output is correct |
| 19 |
Correct |
150 ms |
13256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
11 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
11 ms |
1136 KB |
Output is correct |
| 5 |
Correct |
10 ms |
1136 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 |
2068 ms |
4936 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
