| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 635078 |
2022-08-25T11:46:54 Z |
K4YAN |
ZIGZAG (INOI20_zigzag) |
C++17 |
|
657 ms |
86208 KB |
//Be Name Khoda
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define all(x) x.begin(), x.end()
const ll mxn = 3e5 + 16, INF = 1e16 + 16;
ll n, t, q, w;
vector<ll> g;
char c;
inline void input() {
cin >> n >> t;
for(int i = 0; i < n; i++) {
cin >> q;
g.push_back(q);
}
}
struct item {
ll sz, ans, L, R, bp, bs, kp, ks;
};
struct segtree {
int sz = 1;
item NE = {0, 0, 0, 0, 0, 0, 0, 0};
vector<item> v;
vector<ll> lz, ls;
void init(ll n) {
while(sz < n) sz <<= 1;
v.assign(2 * sz, NE);
lz.assign(2 * sz, 1);
ls.assign(2 * sz, 0);
return;
}
void shift(int x, int lx, int rx) {
if(lz[x] == 0 && ls[x] == 0) return;
ll a = lz[x], b = ls[x];
lz[x] = ls[x] = 0;
v[x].L += b, v[x].R += b;
if(a) {
v[x].L *= -1, v[x].R *= -1;
swap(v[x].kp, v[x].bp);
swap(v[x].ks, v[x].bs);
}
if(rx - lx == 1) return;
if(lz[2 * x + 1]) ls[2 * x + 1] -= b;
else ls[2 * x + 1] += b;
if(lz[2 * x + 2]) ls[2 * x + 2] -= b;
else ls[2 * x + 2] += b;
lz[2 * x + 1] ^= a, lz[2 * x + 2] ^= a;
return;
}//Shift Vaghean doroste
item merge(item a, item b) {
if(a.sz == 0) return b;
if(b.sz == 0) return a;
ll s = a.sz + b.sz, L = a.L, R = b.R, ans = a.ans + b.ans, bp, bs, kp, ks;
if(a.R == b.L) {
kp = a.kp, ks = b.ks, bp = a.bp, bs = b.bs;
return {s, ans, L, R, bp, bs, kp, ks};
}
if(a.R > b.L) {
ans += (1LL * a.bs * b.kp);
if(a.sz & 1) {
if(a.sz == a.bp) {
bp = a.sz + b.kp, kp = 1;
} else {
bp = a.bp, kp = a.kp;
}
} else {
if(a.sz == a.kp) {
kp = a.sz + b.kp, bp = 1;
} else {
bp = a.bp, kp = a.kp;
}
}
if(b.sz & 1) {
if(b.sz == b.ks) {
ks = b.sz + a.bs, bs = 1;
} else {
ks = b.ks, bs = b.bs;
}
} else {
if(b.sz == b.bs) {
bs = b.sz + a.bs, ks = 1;
} else {
ks = b.ks, bs = b.bs;
}
}
return {s, ans, L, R, bp, bs, kp, ks};
}
if(a.R < b.L) {
ans += (1LL * a.ks * b.bp);
if(a.sz & 1) {
if(a.sz == a.kp) {
kp = a.sz + b.bp, bp = 1;
} else {
kp = a.kp, bp = a.bp;
}
} else {
if(a.sz == a.bp) {
bp = a.sz + b.bp, kp = 1;
} else {
bp = a.bp, kp = a.kp;
}
}
if(b.sz & 1) {
if(b.sz == b.bs) {
bs = b.sz + a.ks, ks = 1;
} else {
bs = b.bs, ks = b.ks;
}
} else {
if(b.sz == b.ks) {
ks = b.sz + a.ks, bs = 1;
} else {
bs = b.bs, ks = b.ks;
}
}
return {s, ans, L, R, bp, bs, kp, ks};
}
return NE;
}
void build(vector<ll> &g, int x, int lx, int rx) {
if(rx - lx == 1) {
if(lx < int(g.size())) {
v[x] = {1, 1, g[lx], g[lx], 1, 1, 1, 1};
} return;
}
int m = (lx + rx) >> 1;
build(g, 2 * x + 1, lx, m), build(g, 2 * x + 2, m, rx);
v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
return;
}
void build(vector<ll> & g) {
build(g, 0, 0, sz);
return;
}
void zarb(int l, int r, int x, int lx, int rx) {
shift(x, lx, rx);
if(rx <= l || r <= lx) return;
if(l <= lx && rx <= r) {
lz[x] = 1;
shift(x, lx, rx);
return;
} int m = (lx + rx) >> 1;
zarb(l, r, 2 * x + 1, lx, m);
zarb(l, r, 2 * x + 2, m, rx);
v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
return;
}
void zarb(int l, int r) {
zarb(l, r, 0, 0, sz);
return;
}
void jam(int l, int r, int q, int x, int lx, int rx) {
shift(x, lx, rx);
if(rx <= l || r <= lx) return;
if(l <= lx && rx <= r) {
ls[x] += q;
shift(x, lx, rx);
return;
} int m = (lx + rx) >> 1;
jam(l, r, q, 2 * x + 1, lx, m);
jam(l, r, q, 2 * x + 2, m, rx);
v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
return;
}
void jam(int l, int r, int q) {
jam(l, r, q, 0, 0, sz);
return;
}
item ask(int l, int r, int x, int lx, int rx) {
shift(x, lx, rx);
if(rx <= l || r <= lx) return NE;
if(l <= lx && rx <= r) {
return v[x];
} int m = (lx + rx) >> 1;
item ans = ask(l, r, 2 * x + 1, lx, m);
ans = merge(ans, ask(l, r, 2 * x + 2, m, rx));
v[x] = merge(v[2 * x + 1], v[2 * x + 2]);
return ans;
}
ll ask(int l, int r) {
return ask(l, r, 0, 0, sz).ans;
}
}; segtree st;
inline void solve() {
st.init(n);
st.build(g);
for(int i = 0; i < t; i++) {
cin >> c;
if(c == '*') {
cin >> q >> w; q--;
st.zarb(q, w);
} else if(c == '+') {
ll v;
cin >> q >> w >> v; q--;
st.jam(q, w, v);
} else {
cin >> q >> w; q--;
cout << st.ask(q, w) << "\n";
}
} return;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
input(), solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
657 ms |
86208 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
