이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e12 + 10;
struct node
{
int sum, minSum, minVal, maxVal, lz;
node (int S = 0, int MS = 0, int minV = INF, int maxV = 0) : sum(S), minSum(MS), minVal(minV), maxVal(maxV), lz(-INF) {}
node operator+ (node outro)
{
return node(sum + outro.sum, minSum + outro.minSum, min(minVal, outro.minVal), max(maxVal, outro.maxVal));
}
};
const int MAXN = 3e5 + 10;
array<node, 4*MAXN> seg;
void refresh(int pos, int ini, int fim)
{
if (seg[pos].lz == -INF) return;
int x = seg[pos].lz;
seg[pos] = node(seg[pos].sum, (fim-ini+1)*x, x, x);
if (ini == fim) return;
int e = 2*pos, d = e+1;
seg[e].lz = seg[d].lz = x;
}
void update(int pos, int ini, int fim, int p, int q, int val)
{
refresh(pos, ini, fim);
if (q < ini || p > fim) return;
if (p <= ini && fim <= q)
{
// cerr << val << " at " << ini << " " << fim << '\n';
seg[pos].lz = val;
refresh(pos, ini, fim);
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos, d = e+1;
update(e, ini, m, p, q, val);
update(d, m+1, fim, p, q, val);
seg[pos] = seg[e] + seg[d];
}
void build(int pos, int ini, int fim, const vector<int> &C, const vector<int> &S, int D)
{
if (ini == fim)
{
seg[pos] = node((C[ini]/D)-S[ini]);
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos, d = e+1;
build(e, ini, m, C, S, D);
build(d, m+1, fim, C, S, D);
seg[pos] = seg[e] + seg[d];
}
node query(int pos, int ini, int fim, int p, int q)
{
refresh(pos, ini, fim);
if (q < ini || p > fim) return node();
if (p <= ini && fim <= q) return seg[pos];
int m = (ini + fim) >> 1;
int e = 2*pos, d = e+1;
return (query(e, ini, m, p, q) + query(d, m+1, fim, p, q));
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, D;
cin >> N >> D;
vector<int> C(N+1);
for (int i = 1; i <= N; i++) cin >> C[i];
vector<int> S(N+1); for (int i = 2; i <= N; i++) S[i] = S[i-1] + (int)((C[i]%D) < (C[i-1]%D));
// cerr << "S: "; for (int i = 1; i <= N; i++) cerr << S[i] << " "; cerr << '\n';
build(1, 1, N, C, S, D);
int Q; cin >> Q;
vector<int> resp(Q); vector<vector<pair<int, int>>> queries(N+1);
for (int i = 0; i < Q; i++)
{
int L, R;
cin >> L >> R;
queries[R].emplace_back(L, i);
}
stack<pair<int, int>> s; s.emplace(-INF, 0);
for (int i = 1; i <= N; i++)
{
while (s.top().first >= (C[i]/D)-S[i]) s.pop();
update(1, 1, N, s.top().second+1, i, (C[i]/D)-S[i]);
s.emplace((C[i]/D)-S[i], i);
for (auto [L, id] : queries[i])
{
auto ans = query(1, 1, N, L, i);
// cerr << "L: " << L << ", R: " << i << ", sum: " << ans.sum << ", minSum: " << ans.minSum << ", minVal: " << ans.minVal << '\n';
if (ans.minVal + S[L] < 0) resp[id] = -1;
else resp[id] = ans.sum - ans.minSum;
}
}
for (auto x : resp) cout << x << '\n';
}
# | 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... |