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>
using namespace std;
const int MAX_RAGETREE_SZ = 300005;
int ragetreesum[4 * MAX_RAGETREE_SZ];
int ragetreemin[4 * MAX_RAGETREE_SZ];
int ragetreelazy[4 * MAX_RAGETREE_SZ];
int n;
void pushdown(int idx) {
ragetreelazy[2*idx] += ragetreelazy[idx];
ragetreelazy[2*idx+1] += ragetreelazy[idx];
ragetreelazy[idx] = 0;
}
void pullup(int idx) {
ragetreesum[idx] = ragetreesum[2*idx] + ragetreesum[2*idx+1];
ragetreemin[idx] = min(ragetreemin[2*idx], ragetreemin[2*idx+1]);
}
void ragetreedec(int idx, int lhs, int rhs, int l, int r) {
if(lhs >= l && rhs <= r && ragetreemin[idx] + ragetreelazy[idx] - 1 > 0) {
ragetreelazy[idx]--;
return;
}
if(lhs == rhs) {
ragetreesum[idx]++;
ragetreemin[idx] = 1e9;
}
pushdown(idx);
int mid = (lhs+rhs)/2;
if(mid >= l) ragetreedec(2*idx, lhs, mid, l, r);
if(mid+1 <= r) ragetreedec(2*idx+1, mid+1, rhs, l, r);
pullup(idx);
}
int ragetreequery(int idx, int lhs, int rhs, int l, int r) {
if(lhs >= l && rhs <= r) return ragetreesum[idx];
int ret = 0;
int mid = (lhs+rhs)/2;
if(mid >= l) ret += ragetreequery(2*idx, lhs, mid, l, r);
if(mid+1 <= r) ret += ragetreequery(2*idx+1, mid+1, rhs, l, r);
return ret;
}
void ragetreeinit(int idx, int lhs, int rhs, int *D) {
if(lhs == rhs) {
if(D[lhs] <= 0) {
ragetreesum[idx] = 1;
ragetreemin[idx] = 1e9;
}
else {
ragetreemin[idx] = D[lhs];
}
return;
}
int mid = (lhs+rhs)/2;
ragetreeinit(2*idx, lhs, mid, D);
ragetreeinit(2*idx+1, mid+1, rhs, D);
pullup(idx);
}
void inicjuj(int nn, int k, int *D) {
n = nn;
for(int i = 0; i < n; i++) D[i] = k - D[i];
ragetreeinit(1, 0, n-1, D);
}
// inc [a, b] by 1
void podlej(int a, int b) {
ragetreedec(1, 0, n-1, a, b);
}
// count
int dojrzale(int a, int b) {
return ragetreequery(1, 0, n-1, a, b);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |