이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;
#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"
template<class X, class Y>
bool minz(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
} return false;
}
template<class X, class Y>
bool maxz(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
} return false;
}
const int N = 3e5 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;
int n, q, l, r;
ll d, a[N], tree[N << 2], lz[N << 2], fl[N], ans[N], mn[N << 2], lzmn[N << 2];
vector <pii> qq[N];
void down (int i, int l, int r){
if (!lz[i]) return;
int mid = l + r >> 1;
tree[i << 1] += (mid - l + 1) * lz[i];
tree[i << 1 | 1] += (r - mid) * lz[i];
lz[i << 1] += lz[i];
lz[i << 1 | 1] += lz[i];
lz[i] = 0;
}
void downmn (int i){
if (!lzmn[i]) return;
forr (j, i << 1, i << 1 | 2){
mn[j] += lzmn[i];
lzmn[j] += lzmn[i];
}
lzmn[i] = 0;
}
void addmn (int i, int l, int r, int u, int v, ll val){
if (l > v || r < u) return;
if (l >= u && r <= v){
mn[i] += val;
return;
}
downmn(i);
int mid = l + r >> 1;
addmn(i << 1, l, mid, u, v, val);
addmn(i << 1 | 1, mid + 1, r, u, v, val);
mn[i] = min (mn[i << 1], mn[i << 1 | 1]);
}
ll getmn (int i, int l, int r, int u, int v){
if (l > v || r < u) return mod;
if (l >= u && r <= v) return mn[i];
downmn(i);
int mid = l + r >> 1;
return min(getmn(i << 1, l, mid, u, v), getmn(i << 1 | 1, mid + 1, r, u, v));
}
void add (int i, int l, int r, int u, int v, ll val){
if (l > v || r < u) return;
if (l >= u && r <= v){
tree[i] += (r - l + 1) * val;
lz[i] += val;
return;
}
down(i, l, r);
int mid = l + r >> 1;
add(i << 1, l, mid, u, v, val);
add(i << 1 | 1, mid + 1, r, u, v, val);
tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
void add (int l, int r, ll val){
add(1, 1, n, l, r, val);
}
ll get (int i, int l, int r, int u, int v){
if (l > v || r < u) return 0;
if (l >= u && r <= v) return tree[i];
down(i, l, r);
int mid = l + r >> 1;
return get(i << 1, l, mid, u, v) + get(i << 1 | 1, mid + 1, r, u, v);
}
ll get (int u){
return get(1, 1, n, u, u);
}
ll get (int l, int r){
return get(1, 1, n, l, r);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef kaguya
freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
#endif
cin >> n >> d;
forr (i, 1, n){
cin >> a[i];
}
cin >> q;
forr (i, 1, q){
cin >> l >> r;
qq[r].pb({l, i});
}
forr (i, 1, n){
fl[i] = i;
addmn(1, 1, n, i, i, a[i]);
if (i != 1){
ll cur = i;
while (1){
ll tmp = a[cur - 1] - d * get(cur - 1) - (a[cur] - d * get(cur));
if (tmp <= 0) break;
add(fl[cur - 1], cur - 1, (tmp - 1) / d + 1);
addmn(1, 1, n, fl[cur - 1], cur - 1, -((tmp - 1) / d + 1) * d);
fl[cur] = fl[cur - 1];
}
}
for (pii u : qq[i]){
if (getmn(1, 1, n, u.st, i) < 0) ans[u.nd] = -1;
else ans[u.nd] = get(u.st, i);
}
}
forr (i, 1, q){
cout << ans[i] << "\n";
}
return 0;
}
/*
*/
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void down(int, int, int)':
Main.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'void addmn(int, int, int, int, int, ll)':
Main.cpp:72:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'll getmn(int, int, int, int, int)':
Main.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'void add(int, int, int, int, int, ll)':
Main.cpp:94:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In function 'll get(int, int, int, int, int)':
Main.cpp:108:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
108 | int mid = l + r >> 1;
| ~~^~~
# | 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... |