| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1112191 | zxcigan | Fish 3 (JOI24_fish3) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(time(0));
using ll = long long;
#define int long long
const int N = 2e5 + 1;
void solve() {
int n, d; cin >> n >> d;
vector<int> c(n + 1), pref (n + 1), a(n + 1), b(n + 1);
bool flag = 1;
for (int i = 1; i <= n; ++i) {
cin >> c[i];
if (i != 1 && c[i] > c[i - 1]) flag = 0;
a[i] = c[i] / d;
b[i] = c[i] % d;
pref[i] = pref[i - 1] + c[i];
}
int q; cin >> q;
if (flag) {
vector<int> p2 (n + 1, 0);
vector<int> p3 (n + 1, 0);
vector<int> p4 (n + 1, 0);
for (int i = 1; i < n; ++i) p4[i] = p4[i - 1] + (b[i] > b[i + 1] ? i : 0);
for (int i = 1; i < n; ++i) p3[i] = p3[i - 1] + bool (b[i] > b[i + 1]);
for (int i = 1; i <= n; ++i) p2[i] = p2[i - 1] + a[i];
while (q--) {
int ans = 0;
int l, r, res = 0; cin >> l >> r;
int mnD = a[r], C = 0, kol = p3[r] - p3[l - 1];
bad = 0;
r -= 1;
ans = p2[r] - p2[l - 1];
ans -= mnD * (r - l + 1);
C = (p4[r] - p4[l - 1]) - (l + 1) * kol;
ans += C;
if (mnD >= kol) cout << ans << '\n';
else cout << "-1\n";
}
return;
}
if (d == 1) {
vector<int> smalL (n + 1, 0);
vector<int>v;
for (int i = 1; i <= n; ++i) {
while ((int)v.size() && c[v.back()] >= c[i]) v.pop_back();
if ((int)v.size()) smalL[i] = v.back();
v.push_back(i);
}
vector<vector<int>> binup (20, vector<int> (n + 1));
vector<vector<int>> cost (20, vector<int> (n + 1));
for (int i = n; i >= 1; --i) {
binup[0][i] = smalL[i];
cost[0][i] += pref[i] - pref[smalL[i]] - (i - smalL[i]) * c[i];
}
for (int j = 1; j < 20; ++j) {
for (int i = 1; i <= n; ++i) {
binup[j][i] = binup[j - 1][binup[j - 1][i]];
cost[j][i] = cost[j - 1][i] + cost[j - 1][binup[j - 1][i]];
}
}
while (q--) {
int l, r;
cin >> l >> r;
int ans = 0;
int v = r;
for (int pw = 19; pw >= 0; --pw) {
if (binup[pw][v] > l) {
ans += cost[pw][v];
v = binup[pw][v];
}
}
int id = max (smalL[v] + 1, l);
ans += pref[v] - pref[id - 1] - (v - id + 1) * c[v];
cout << ans << '\n';
}
return;
}
if (n <= (int)3e3 && q <= (int)3e3) {
while (q--) {
int l, r; cin >> l >> r;
vector<int> a = c;
int res = 0;
bool bad = 0;
for (int i = r - 1; i >= l; --i) {
if (a[i] > a[i + 1]) {
int p = (a[i] - a[i + 1] + d - 1) / d;
res += p;
a[i] -= p * d;
}
if (a[i] < 0) {
bad = 1;
break;
}
}
cout << (!bad ? res : -1) << '\n';
}
return;
}
vector<int> mxl (n + 1);
for (int i = 1; i <= n; ++i) {
if (c[i]) mxl[i] = mxl[i - 1] + 1;
}
while (q--) {
int l, r; cin >> l >> r;
int ans = 0, wr = r;
r -= mxl[r];
if (r >= l) ans = pref[r] - pref[l - 1];
if (ans) {
if (d > 1) {
cout << "-1\n";
continue;
}
}
cout << ans << '\n';
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
int T = 1;
while (T--) solve();
return 0;
}