# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
979444 |
2024-05-11T01:48:13 Z |
penguin133 |
Fish 3 (JOI24_fish3) |
C++17 |
|
224 ms |
47484 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, d, q, A[300005], val[300005], P[300005], grr[300005];
vector <pii> Q;
int ans[300005];
pi brr[300005];
void dnc(int l, int r, vector <pii> &qu){
if(l >= r)return;
int mid = (l + r) >> 1;
vector <pii> lft, rgt, gd;
for(auto i : qu){
if(i.fi > mid)rgt.push_back(i);
else if(i.se.fi <= mid)lft.push_back(i);
else gd.push_back(i);
}
dnc(l, mid, lft);
dnc(mid + 1, r, rgt);
brr[mid + 1] = {0, 0};
int cur_sum = 0, cur_one = 0;
stack <pi> s;
s.push({1e18, mid});
for(int i = mid + 2; i <= r; i++){
if(A[i] >= A[i - 1])s.push({(A[i] - A[i - 1]) / d, i - 1});
else{
int tmp = (A[i - 1] - A[i] + d - 1) / d;
cur_sum += tmp * (i - 1 - s.top().se);
if(s.top().se == mid)cur_one += tmp;
while(!s.empty() && tmp){
pi x = s.top();
s.pop();
if(x.fi > tmp){
x.fi -= tmp;
s.push(x);
break;
}
tmp -= x.fi;
assert(!s.empty());
cur_sum += (x.se - s.top().se) * tmp;
if(s.top().se == mid)cur_one += tmp;
}
}
brr[i] = {cur_sum, cur_one};
}
int prv = A[mid], cur = 0;
brr[mid] = {0, A[mid]};
val[mid] = 0;
for(int i = mid - 1; i >= l; i--){
if(A[i] <= prv){
brr[i] = {cur, A[i]};
val[i] = (prv - A[i]) / d;
prv = A[i];
continue;
}
int ops = (A[i] - prv + d - 1) / d;
val[i] = 0;
prv = A[i] - ops * d;
cur += ops;
brr[i] = {cur, prv};
}
P[l - 1] = grr[l - 1] = 0;
for(int i = l; i <= mid; i++)P[i] = P[i - 1] + val[i], grr[i] = grr[i - 1] + val[i] * (i + 1);
for(auto i : gd){
int lend = i.fi, rend = i.se.fi;
if(brr[lend].se < 0 || A[mid + 1] - brr[rend].se * d < 0){
ans[i.se.se] = -1;
continue;
}
int lo = lend, hi = mid, tmp = lo, ops = 0, ops_one = 0;
int rem = A[mid + 1] - brr[rend].se * d;
int req = (A[mid] - rem + d - 1) / d;
req = max(req, 0ll);
while(lo <= hi){
int mm = (lo + hi) >> 1;
if(P[mid] - P[mm - 1] >= req)tmp = mm, lo = mm + 1;
else hi = mm - 1;
}
//cout << lend << ' ' << rend << ' ' << tmp << ' ' << req << ' ' << rem << '\n';
//cout << P[mid] - P[tmp - 1] << '\n';
if(P[mid] - P[tmp - 1] <= req){
ops = req * (mid - lend + 1) - (grr[mid] - grr[tmp - 1]) + lend * (P[mid] - P[tmp - 1]);
if(tmp == lend)ops_one += req - P[mid] + P[tmp - 1];
}
else{
int x = P[mid] - P[tmp];
ops += req * (mid - lend + 1) - (grr[mid] - grr[tmp]) + lend * x;
rem = req - x;
ops -= rem * (tmp + 1);
ops += lend * rem;
}
if(brr[lend].se - ops_one * d < 0)ans[i.se.se] = -1;
else ans[i.se.se] = brr[lend].fi + brr[rend].fi + ops;
}
}
void solve(){
cin >> n >> d;
for(int i = 1; i <= n; i++)cin >> A[i];
for(int i = 1; i < n; i++){
if(A[i] < A[i + 1]){
val[i] = (A[i + 1] - A[i]) / d;
}
P[i] = P[i - 1] + val[i];
grr[i] = grr[i - 1] + val[i] * (i + 1);
}
cin >> q;
/*
while(q--){
int l, r; cin >> l >> r;
int cur = 0, f = 1, prv = A[r];
for(int i = r - 1; i >= l; i--){
int df = A[i] - prv;
if(df < 0){
prv = A[i];
continue;
}
int tmp = (df + d - 1) / d;
if(A[i] - tmp * d < 0){
f = 0;
break;
}
prv = A[i] - tmp * d;
cur += (df + d - 1) / d;
}
if(!f){
cout << -1 << '\n';
continue;
}
cout << cur << '\n';
}
*/
for(int i = 1; i <= q; i++){
int l, r;
cin >> l >> r;
if(l == r)ans[i] = 0;
else Q.push_back({l, {r, i}});
}
dnc(1, n, Q);
for(int i = 1; i <= q; i++)cout << ans[i] << '\n';
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
Main.cpp:153:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
153 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6488 KB |
Output is correct |
3 |
Correct |
1 ms |
8676 KB |
Output is correct |
4 |
Correct |
3 ms |
7004 KB |
Output is correct |
5 |
Correct |
3 ms |
8796 KB |
Output is correct |
6 |
Correct |
3 ms |
6748 KB |
Output is correct |
7 |
Correct |
2 ms |
6748 KB |
Output is correct |
8 |
Correct |
3 ms |
8796 KB |
Output is correct |
9 |
Correct |
3 ms |
8796 KB |
Output is correct |
10 |
Correct |
2 ms |
6748 KB |
Output is correct |
11 |
Correct |
3 ms |
8796 KB |
Output is correct |
12 |
Correct |
3 ms |
8796 KB |
Output is correct |
13 |
Correct |
2 ms |
8796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
155 ms |
40868 KB |
Output is correct |
2 |
Correct |
157 ms |
42412 KB |
Output is correct |
3 |
Correct |
61 ms |
32940 KB |
Output is correct |
4 |
Correct |
137 ms |
43184 KB |
Output is correct |
5 |
Correct |
140 ms |
38568 KB |
Output is correct |
6 |
Correct |
143 ms |
40360 KB |
Output is correct |
7 |
Correct |
141 ms |
41904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
32688 KB |
Output is correct |
2 |
Correct |
211 ms |
46316 KB |
Output is correct |
3 |
Correct |
209 ms |
39856 KB |
Output is correct |
4 |
Correct |
204 ms |
47484 KB |
Output is correct |
5 |
Correct |
206 ms |
47024 KB |
Output is correct |
6 |
Correct |
163 ms |
40396 KB |
Output is correct |
7 |
Correct |
185 ms |
41128 KB |
Output is correct |
8 |
Correct |
174 ms |
40248 KB |
Output is correct |
9 |
Correct |
174 ms |
41448 KB |
Output is correct |
10 |
Correct |
181 ms |
40488 KB |
Output is correct |
11 |
Correct |
171 ms |
40804 KB |
Output is correct |
12 |
Correct |
175 ms |
41696 KB |
Output is correct |
13 |
Correct |
172 ms |
43692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
141 ms |
40332 KB |
Output is correct |
2 |
Correct |
158 ms |
42416 KB |
Output is correct |
3 |
Correct |
90 ms |
35268 KB |
Output is correct |
4 |
Correct |
178 ms |
41688 KB |
Output is correct |
5 |
Correct |
163 ms |
40044 KB |
Output is correct |
6 |
Correct |
171 ms |
45232 KB |
Output is correct |
7 |
Correct |
157 ms |
39596 KB |
Output is correct |
8 |
Correct |
173 ms |
41132 KB |
Output is correct |
9 |
Correct |
148 ms |
43060 KB |
Output is correct |
10 |
Correct |
139 ms |
40628 KB |
Output is correct |
11 |
Correct |
177 ms |
40080 KB |
Output is correct |
12 |
Correct |
161 ms |
41184 KB |
Output is correct |
13 |
Correct |
181 ms |
47124 KB |
Output is correct |
14 |
Correct |
160 ms |
40668 KB |
Output is correct |
15 |
Correct |
191 ms |
45456 KB |
Output is correct |
16 |
Correct |
147 ms |
40112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6488 KB |
Output is correct |
2 |
Correct |
1 ms |
6488 KB |
Output is correct |
3 |
Correct |
1 ms |
8676 KB |
Output is correct |
4 |
Correct |
3 ms |
7004 KB |
Output is correct |
5 |
Correct |
3 ms |
8796 KB |
Output is correct |
6 |
Correct |
3 ms |
6748 KB |
Output is correct |
7 |
Correct |
2 ms |
6748 KB |
Output is correct |
8 |
Correct |
3 ms |
8796 KB |
Output is correct |
9 |
Correct |
3 ms |
8796 KB |
Output is correct |
10 |
Correct |
2 ms |
6748 KB |
Output is correct |
11 |
Correct |
3 ms |
8796 KB |
Output is correct |
12 |
Correct |
3 ms |
8796 KB |
Output is correct |
13 |
Correct |
2 ms |
8796 KB |
Output is correct |
14 |
Correct |
155 ms |
40868 KB |
Output is correct |
15 |
Correct |
157 ms |
42412 KB |
Output is correct |
16 |
Correct |
61 ms |
32940 KB |
Output is correct |
17 |
Correct |
137 ms |
43184 KB |
Output is correct |
18 |
Correct |
140 ms |
38568 KB |
Output is correct |
19 |
Correct |
143 ms |
40360 KB |
Output is correct |
20 |
Correct |
141 ms |
41904 KB |
Output is correct |
21 |
Correct |
77 ms |
32688 KB |
Output is correct |
22 |
Correct |
211 ms |
46316 KB |
Output is correct |
23 |
Correct |
209 ms |
39856 KB |
Output is correct |
24 |
Correct |
204 ms |
47484 KB |
Output is correct |
25 |
Correct |
206 ms |
47024 KB |
Output is correct |
26 |
Correct |
163 ms |
40396 KB |
Output is correct |
27 |
Correct |
185 ms |
41128 KB |
Output is correct |
28 |
Correct |
174 ms |
40248 KB |
Output is correct |
29 |
Correct |
174 ms |
41448 KB |
Output is correct |
30 |
Correct |
181 ms |
40488 KB |
Output is correct |
31 |
Correct |
171 ms |
40804 KB |
Output is correct |
32 |
Correct |
175 ms |
41696 KB |
Output is correct |
33 |
Correct |
172 ms |
43692 KB |
Output is correct |
34 |
Correct |
141 ms |
40332 KB |
Output is correct |
35 |
Correct |
158 ms |
42416 KB |
Output is correct |
36 |
Correct |
90 ms |
35268 KB |
Output is correct |
37 |
Correct |
178 ms |
41688 KB |
Output is correct |
38 |
Correct |
163 ms |
40044 KB |
Output is correct |
39 |
Correct |
171 ms |
45232 KB |
Output is correct |
40 |
Correct |
157 ms |
39596 KB |
Output is correct |
41 |
Correct |
173 ms |
41132 KB |
Output is correct |
42 |
Correct |
148 ms |
43060 KB |
Output is correct |
43 |
Correct |
139 ms |
40628 KB |
Output is correct |
44 |
Correct |
177 ms |
40080 KB |
Output is correct |
45 |
Correct |
161 ms |
41184 KB |
Output is correct |
46 |
Correct |
181 ms |
47124 KB |
Output is correct |
47 |
Correct |
160 ms |
40668 KB |
Output is correct |
48 |
Correct |
191 ms |
45456 KB |
Output is correct |
49 |
Correct |
147 ms |
40112 KB |
Output is correct |
50 |
Correct |
200 ms |
40368 KB |
Output is correct |
51 |
Correct |
157 ms |
41564 KB |
Output is correct |
52 |
Correct |
169 ms |
38064 KB |
Output is correct |
53 |
Correct |
167 ms |
42800 KB |
Output is correct |
54 |
Correct |
176 ms |
47004 KB |
Output is correct |
55 |
Correct |
224 ms |
45996 KB |
Output is correct |
56 |
Correct |
149 ms |
39060 KB |
Output is correct |
57 |
Correct |
141 ms |
40496 KB |
Output is correct |
58 |
Correct |
136 ms |
40112 KB |
Output is correct |
59 |
Correct |
175 ms |
45756 KB |
Output is correct |
60 |
Correct |
167 ms |
41268 KB |
Output is correct |
61 |
Correct |
165 ms |
40900 KB |
Output is correct |
62 |
Correct |
164 ms |
41212 KB |
Output is correct |
63 |
Correct |
171 ms |
44464 KB |
Output is correct |
64 |
Correct |
165 ms |
41256 KB |
Output is correct |