제출 #1254981

#제출 시각아이디문제언어결과실행 시간메모리
1254981MisterReaperFish 2 (JOI22_fish2)C++20
100 / 100
1908 ms74464 KiB
// File B.cpp created on 08.08.2025 at 11:52:11 #include <bits/stdc++.h> using i64 = long long; #ifdef DEBUG #include "/home/ahmetalp/Desktop/Workplace/debug.h" #else #define debug(...) void(23) #endif constexpr int max_N = int(1E5) + 5; int N; int A[max_N]; struct Info { int l, r; std::vector<int> pntl; std::vector<int> frql; std::vector<i64> suml; std::vector<int> pntr; std::vector<int> frqr; std::vector<i64> sumr; Info() {} Info(int x) { l = r = x; pntl = {x}; frql = {1}; suml = {A[x]}; pntr = {x}; frqr = {1}; sumr = {A[x]}; } } tree[max_N << 1]; void clear(std::vector<int>& pnt, std::vector<int>& frq, std::vector<i64>& sum) { std::vector<int> npnt; std::vector<int> nfrq; std::vector<i64> nsum; for (int i = 0; i < int(pnt.size()); ++i) { if (frq[i]) { npnt.emplace_back(pnt[i]); nfrq.emplace_back(frq[i]); nsum.emplace_back(sum[i]); } } pnt = std::move(npnt); frq = std::move(nfrq); sum = std::move(nsum); } Info operator+ (const Info& lhs, const Info& rhs) { Info res; res.l = lhs.l; res.r = rhs.r; { int sizl = int(lhs.pntl.size()); int sizr = int(rhs.pntl.size()); int n = sizl + sizr; res.pntl.insert(res.pntl.end(), lhs.pntl.begin(), lhs.pntl.end()); res.pntl.insert(res.pntl.end(), rhs.pntl.begin(), rhs.pntl.end()); res.frql.resize(n); res.suml.resize(n); for (int i = 0; i < n; ++i) { if (i < sizl) { res.suml[i] = lhs.suml[i]; } else { res.suml[i] = lhs.suml.back() + rhs.suml[i - sizl]; } } { // Case 1: sol childimin sola yapisik ama saga yapisik olmayani ekle for (int i = 0; i < sizl - 1; ++i) { res.frql[i] += lhs.frql[i]; } } { // Case 2: sol childimin saga yapisik olanlari sola ve saga buyutup ekle int m = int(lhs.pntr.size()); int l = m, r = -1; for (int i = m - 1; i >= 0; --i) { l = std::min(l, i); while (true) { i64 sum = lhs.sumr[l] + (r == -1 ? 0 : rhs.suml[r]); if (r != sizr - 1 && sum >= A[r == -1 ? rhs.l : (rhs.pntl[r] + 1)]) { r++; continue; } if (l != 0 && sum >= A[lhs.pntr[l] - 1]) { l--; continue; } break; } if (l == 0) { res.frql[sizl + r] += lhs.frqr[i]; } } } { // Case 3: sag childimin sola yapisik kaplayanlari buyutup eger sola yapisirlarsa ekle int m = int(lhs.pntr.size()); int l = m, r = -1; for (int i = 0; i < sizr; ++i) { r = std::max(r, i); while (true) { i64 sum = (l == m ? 0 : lhs.sumr[l]) + rhs.suml[r]; if (r != sizr - 1 && A[rhs.pntl[r] + 1] <= sum) { r++; continue; } if (l != 0 && A[l == m ? lhs.r : (lhs.pntr[l] - 1)] <= sum) { l--; continue; } break; } if (l == 0) { res.frql[sizl + r] += rhs.frql[i]; } } } } { int sizl = int(lhs.pntr.size()); int sizr = int(rhs.pntr.size()); int n = sizl + sizr; res.pntr.insert(res.pntr.end(), lhs.pntr.begin(), lhs.pntr.end()); res.pntr.insert(res.pntr.end(), rhs.pntr.begin(), rhs.pntr.end()); res.frqr.resize(n); res.sumr.resize(n); for (int i = 0; i < n; ++i) { if (i < sizl) { res.sumr[i] = lhs.sumr[i] + rhs.sumr[0]; } else { res.sumr[i] = rhs.sumr[i - sizl]; } } { // Case 1: sag childimin saga yapisik ama sola yapisik olmayani ekle for (int i = 1; i < sizr; ++i) { res.frqr[sizl + i] += rhs.frqr[i]; } } { // Case 2: sag childimin sola yapisik olanlari sola ve saga buyutup ekle int m = int(rhs.pntl.size()); int l = sizl, r = -1; for (int i = 0; i < m; ++i) { r = std::max(r, i); while (true) { i64 sum = (l == sizl ? 0 : lhs.sumr[l]) + rhs.suml[r]; if (r != m - 1 && sum >= A[rhs.pntl[r] + 1]) { r++; continue; } if (l != 0 && sum >= A[l == sizl ? lhs.r : (lhs.pntr[l] - 1)]) { l--; continue; } break; } if (r == m - 1) { res.frqr[l] += rhs.frql[i]; } } } { // Case 3: sol childimin saga yapisik kaplayanlari buyutup eger saga yapisirlarsa ekle int m = int(rhs.pntl.size()); int l = sizl, r = -1; for (int i = sizl - 1; i >= 0; --i) { l = std::min(l, i); while (true) { i64 sum = lhs.sumr[l] + (r == -1 ? 0 : rhs.suml[r]); if (r != m - 1 && sum >= A[r == -1 ? rhs.l : (rhs.pntl[r] + 1)]) { r++; continue; } if (l != 0 && sum >= A[lhs.pntr[l] - 1]) { l--; continue; } break; } if (r == m - 1) { res.frqr[l] += lhs.frqr[i]; } } } } clear(res.pntl, res.frql, res.suml); clear(res.pntr, res.frqr, res.sumr); return res; } #define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1) void build(int v, int l, int r) { if (l == r) { tree[v] = {l}; return; } def; build(lv, l, mid); build(rv, mid + 1, r); tree[v] = tree[lv] + tree[rv]; debug(l, r); debug(tree[v].l, tree[v].r); debug(tree[v].pntl); debug(tree[v].frql); debug(tree[v].suml); debug(tree[v].pntr); debug(tree[v].frqr); debug(tree[v].sumr); // if (l == 0 && r == 4) exit(0); } void modify(int v, int l, int r, int p, int x) { if (l == r) { A[p] = x; tree[v] = {p}; return; } def; if (p <= mid) { modify(lv, l, mid, p, x); } else { modify(rv, mid + 1, r, p, x); } tree[v] = tree[lv] + tree[rv]; } Info get(int v, int l, int r, int ql, int qr) { if (ql == l && r == qr) { return tree[v]; } def; if (qr <= mid) { return get(lv, l, mid, ql, qr); } else if (mid + 1 <= ql) { return get(rv, mid + 1, r, ql, qr); } else { return get(lv, l, mid, ql, mid) + get(rv, mid + 1, r, mid + 1, qr); } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> N; for (int i = 0; i < N; ++i) { std::cin >> A[i]; } build(0, 0, N - 1); // exit(0); int Q; std::cin >> Q; for (int _ = 0; _ < Q; ++_) { int TP; std::cin >> TP; if (TP == 1) { int P, X; std::cin >> P >> X; --P; modify(0, 0, N - 1, P, X); } else { int L, R; std::cin >> L >> R; --L, --R; auto nd = get(0, 0, N - 1, L, R); std::cout << nd.frql.back() << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...