Submission #1259512

#TimeUsernameProblemLanguageResultExecution timeMemory
1259512mohammad86ZIGZAG (INOI20_zigzag)C++20
100 / 100
541 ms62552 KiB
#include <bits/stdc++.h> using namespace std; // define endl "\n" typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int maxN = 3e5 +100; ll arr[maxN]; struct node { int nxt1, nxt2, prv1, prv2; ll cnt; int l, r; ll first, last; } seg[4 * maxN]; node mergenode(node &node1, node &node2) { int l1 = node1.r - node1.l; int l2 = node2.r - node2.l; node res; ll a = node1.last; ll b = node2.first; res.cnt = node1.cnt + node2.cnt; res.nxt1 = node1.nxt1; res.nxt2 = node1.nxt2; res.prv1 = node2.prv1; res.prv2 = node2.prv2; res.l = node1.l; res.r = node2.r; res.first = node1.first; res.last = node2.last; if (a < b) { res.cnt += 1LL * (node1.r - node1.prv1) * (node2.nxt2 - node2.l + 1); if (node1.prv1 == node1.l) { if (l1 & 1) { res.nxt1 = node2.nxt2; } else { res.nxt2 = node2.nxt2; } } if (node2.nxt2 == node2.r - 1) { if (l2 & 1) { res.prv2 = node1.prv1; } else { res.prv1 = node1.prv1; } } } else if (a > b) { res.cnt += 1LL * (node1.r - node1.prv2) * (node2.nxt1 - node2.l + 1); if (node1.prv2 == node1.l) { if (l1 & 1) { res.nxt2 = node2.nxt1; } else { res.nxt1 = node2.nxt1; } } if (node2.nxt1 == node2.r - 1) { if (l2 & 1) { res.prv1 = node1.prv2; } else { res.prv2 = node1.prv2; } } } return res; } void init(int id, int L, int R) { if (L + 1 == R) { seg[id] = {L, L, L, L, 1, L, R, arr[L], arr[L]}; return; } int mid = (L + R) >> 1; init(id << 1, L, mid); init(id << 1 | 1, mid, R); /*cout << seg[id << 1].cnt << " " << seg[id << 1].l << " " << seg[id << 1].r << " " << seg[id << 1].prv1 << " " << seg[id << 1].prv2 << endl; cout << seg[id << 1 | 1].cnt << " " << seg[id << 1 | 1].l << " " << seg[id << 1 | 1].r << endl;*/ seg[id] = mergenode(seg[id << 1], seg[id << 1 | 1]); /*cout << seg[id].cnt << endl;*/ } ll lazy[4 * maxN]; bool rev[4 * maxN]; void update_lazy(int id, int L, int R) { if (L + 1 < R) { int lc = id << 1; int rc = id << 1 | 1; if (rev[id]) { rev[lc] ^= rev[id]; rev[rc] ^= rev[id]; lazy[lc] *= -1; lazy[rc] *= -1; } lazy[lc] += lazy[id]; lazy[rc] += lazy[id]; } if (rev[id]) { swap(seg[id].nxt1, seg[id].nxt2); swap(seg[id].prv1, seg[id].prv2); seg[id].first *= -1; seg[id].last *= -1; rev[id] = 0; } if (lazy[id] != 0) { seg[id].first += lazy[id]; seg[id].last += lazy[id]; lazy[id] = 0; } } void update(int id, int L, int R, int l, int r, int x) { update_lazy(id, L, R); if (l == L && r == R) { lazy[id] += x; update_lazy(id, L, R); return; } int mid = (L + R) >> 1; if (l < mid) update(id << 1 | 0, L, mid, l, min(mid, r), x); if (r > mid) update(id << 1 | 1, mid, R, max(l, mid), r, x); update_lazy(id << 1 | 0, L, mid); update_lazy(id << 1 | 1, mid, R); seg[id] = mergenode(seg[id << 1], seg[id << 1 | 1]); } void reve(int id, int L, int R, int l, int r) { update_lazy(id, L, R); if (l == L && r == R) { rev[id] = 1; update_lazy(id, L, R); return; } int mid = (L + R) >> 1; if (l < mid) reve(id << 1 | 0, L, mid, l, min(mid, r)); if (r > mid) reve(id << 1 | 1, mid, R, max(l, mid), r); update_lazy(id << 1 | 0, L, mid); update_lazy(id << 1 | 1, mid, R); seg[id] = mergenode(seg[id << 1], seg[id << 1 | 1]); } vector<node> nodes; void get(int id, int L, int R, int l, int r) { update_lazy(id, L, R); if (l == L && r == R) { nodes.push_back(seg[id]); return; } int mid = (L + R) >> 1; if (l < mid) get(id << 1 | 0, L, mid, l, min(mid, r)); if (r > mid) get(id << 1 | 1, mid, R, max(l, mid), r); } int main () { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> arr[i]; } init(1, 1, n + 1); for (int i = 0; i < q; i++) { char type; int l, r; cin >> type >> l >> r; if (type == '+') { int x; cin >> x; update(1, 1, n + 1, l, r + 1, x); } else if (type == '*') { reve(1, 1, n + 1, l, r + 1); } else { nodes.clear(); get(1, 1, n + 1, l, r + 1); node res = nodes[0]; for (int i = 1; i < nodes.size(); i++) { res = mergenode(res, nodes[i]); } cout << res.cnt << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...