이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
const int mod = 998244353, N = 300005;
struct Seg {
int l, r, m;
ll lz, sum;
Seg* ch[2];
Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), lz(0), sum(0) {
if (r - l > 1) {
ch[0] = new Seg(l, m);
ch[1] = new Seg(m, r);
}
}
void pull() {
sum = ch[0]->sum + ch[1]->sum;
}
void give(ll x) {
lz += x, sum += x * (r - l);
}
void push() {
if (!lz) {
return;
}
ch[0]->give(lz), ch[1]->give(lz), lz = 0;
}
void add(int a, int b, ll v) {
if (a <= l && r <= b) {
give(v);
} else {
push();
if (a < m) {
ch[0]->add(a, b, v);
}
if (m < b) {
ch[1]->add(a, b, v);
}
pull();
}
}
ll query(int a, int b) {
if (a <= l && r <= b) {
return sum;
}
push();
ll ans = 0;
if (a < m) {
ans += ch[0]->query(a, b);
}
if (m < b) {
ans += ch[1]->query(a, b);
}
return ans;
}
};
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n;
ll d;
cin >> n >> d;
vector <ll> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
b[i] = a[i] % d, a[i] /= d;
}
// b[i] > b[i + 1] -> a[i] + add[i] <= a[i + 1] + add[i + 1]
vector <int> add(n);
for (int i = 1; i < n; ++i) if (b[i - 1] > b[i]) {
add[i - 1]++;
}
for (int i = n - 2; i >= 0; --i) {
add[i] += add[i + 1];
}
vector <ll> pre_a(n + 1);
for (int i = 0; i < n; ++i) {
a[i] += add[i];
pre_a[i + 1] = pre_a[i] + a[i];
}
int q;
cin >> q;
vector <vector <pii>> queries(n + 1);
for (int i = 0, l, r; i < q; ++i) {
cin >> l >> r, --l, --r;
queries[r].emplace_back(l, i);
}
Seg root(0, n);
vector <array <ll, 3>> stk;
vector <ll> ans(q);
for (int i = 0; i < n; ++i) {
// push i
int lstl = i;
while (!stk.empty() && stk.back()[2] >= a[i]) {
root.add(stk.back()[0], stk.back()[1], -stk.back()[2]);
lstl = stk.back()[0];
stk.pop_back();
}
root.add(lstl, i + 1, a[i]);
stk.pb({lstl, i + 1, a[i]});
// handle query
for (auto [l, id] : queries[i]) {
ll suma = root.query(l, i + 1);
ll lst = root.query(l, l + 1);
if (lst - add[l] < 0) {
ans[id] = -1;
} else {
ans[id] = (pre_a[i + 1] - pre_a[l]) - suma;
}
}
}
for (int i = 0; i < q; ++i) {
cout << ans[i] << '\n';
}
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In constructor 'Seg::Seg(int, int)':
Main.cpp:13:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
13 | Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), lz(0), sum(0) {
| ~~^~~
# | 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... |