| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 634868 |
2022-08-25T07:28:09 Z |
K4YAN |
ZIGZAG (INOI20_zigzag) |
C++17 |
|
865 ms |
85580 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;
q = max(a.ks, a.bs);
if(q < a.sz) {
ans += (q * (q - 1) / 2);
}
q = max(b.bp, b.kp);
if(q < b.sz) {
ans += (q * (q - 1) / 2);
}
return {s, ans, L, R, bp, bs, kp, ks};
}
if(a.R > b.L) {
if(a.sz > a.bs) {
if(b.kp < b.sz) {
q = a.bs + b.kp;
ans += (q * (q - 1) / 2);
bp = a.bp, bs = b.bs, kp = a.kp, ks = b.ks;
return {s, ans, L, R, bp, bs, kp, ks};
} else {
bp = a.bp, kp = a.kp;
if(b.sz & 1) {
bs = 1, ks = b.sz + a.bs;
} else {
bs = b.sz + a.bs, ks = 1;
} return {s, ans, L, R, bp, bs, kp, ks};
} ///okay
}
else if(a.sz == a.bs) {
if(b.kp < b.sz) {
bs = b.bs, ks = b.ks;
if(a.sz & 1) {
bp = a.sz + b.kp, kp = 1;
} else {
kp = a.sz + b.kp, bp = 1;
} return {s, ans, L, R, bp, bs, kp, ks};
} else if(b.kp == b.sz) {
if(a.sz & 1) {
kp = 1, bp = s;
} else {
kp = s, bp = 1;
} if(b.sz & 1) {
bs = 1, ks = s;
} else {
bs = s, ks = 1;
} return {s, ans, L, R, bp, bs, kp, ks};
}// okay
}
}
if(a.R < b.L) {
if(b.sz > b.bp) {
if(a.sz > a.ks) {
q = a.ks + b.bp;
ans += (q * (q - 1) / 2);
bp = a.bp, bs = b.bs, kp = a.kp, ks = b.ks;
return {s, ans, L, R, bp, bs, kp, ks};
} else if(a.sz == a.ks) {
bs = b.bs, ks = b.ks;
if(a.sz & 1) {
bp = 1, kp = a.sz + b.bp;
} else {
bp = a.sz + b.bp, kp = 1;
} return {s, ans, L, R, bp, bs, kp, ks};
}
} else if(b.sz == b.bp) {
if(a.sz > a.ks) { //sz, ans, L, R, bp, bs, kp, ks
kp = a.kp, bp = a.bp;
if(b.sz & 1) {
bs = b.sz + a.ks, ks = 1;
} else {
ks = b.sz + a.ks, bs = 1;
} return {s, ans, L, R, bp, bs, kp, ks};
} else if(a.sz == a.ks) {
if(b.sz & 1) {
bs = s, ks = 1;
} else {
ks = s, bs = 1;
} if(a.sz & 1) {
kp = s, bp = 1;
} else {
bp = s, kp = 1;
} 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, 0, 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;
}
item ask(int l, int r) {
return ask(l, r, 0, 0, sz);
}
}; 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--;
item d;
d = st.ask(q, w);
ll ans = d.ans;
q = max(d.bp, d.kp);
w = max(d.bs, d.ks);
if(q < d.sz) {
ans += (q * (q - 1) / 2);
ans += (w * (w - 1) / 2);
} else {
ans += (q * (q - 1) / 2);
} ans += d.sz;
cout << ans << "\n";
}
} return;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
input(), solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
865 ms |
85580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
