# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
911211 | cadmiumsky | Fish 2 (JOI22_fish2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
int check(vector<int>& v, int p, int l, int r) {
priority_queue<pii, vector<pii>, greater<pii>> heap;
heap.emplace(v[p - 1], p - 1);
heap.emplace(v[p + 1], p + 1);
int S = v[p];
while(!heap.empty()) {
auto [C, poz] = heap.top();
heap.pop();
if(poz > r || poz < l) continue;
if(S < C) return 0;
//cerr << S << ' ' << C << '\t' << p << ' ' << poz << '\n';
S += C;
if(p < poz) heap.emplace(v[poz + 1], poz + 1);
if(p > poz) heap.emplace(v[poz - 1], poz - 1);
}
return 1;
}
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n, q;
cin >> n;
vector<int> v(n + 1);
for(auto &x : v | views::drop(1)) cin >> x;
cin >> q;
v.emplace_back(0);
for(int TC = 0, t, x, y; TC < q; TC++) {
cin >> t >> x >> y;
if(t == 1)
v[x] = y;
else {
int cnt = 0;
for(int i = x; i <= y; i++)
cnt += check(v, i, x, y);
cout << cnt << '\n';
}
}
}
/**
Anul asta nu se da centroid
-- Rugaciunile mele
*/