# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
985562 |
2024-05-18T08:06:35 Z |
maomao90 |
Fish 3 (JOI24_fish3) |
C++17 |
|
483 ms |
52968 KB |
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 300005;
struct Block {
int l, r;
ll lc, rc;
};
int n;
ll d;
ll c[MAXN];
int q;
vii rl[MAXN];
ll ans[MAXN];
vector<Block> stk;
#define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
ll sm[MAXN * 4], lz[MAXN * 4];
void apply(int u, int lo, int hi, ll x) {
lz[u] += x;
sm[u] += x * (hi - lo + 1);
}
void propo(int u, int lo, int hi) {
if (lz[u] == 0) {
return;
}
MLR;
apply(lc, lo, mid, lz[u]);
apply(rc, mid + 1, hi, lz[u]);
lz[u] = 0;
}
void incre(int s, int e, ll x, int u = 1, int lo = 1, int hi = n) {
if (lo >= s && hi <= e) {
apply(u, lo, hi, x);
return;
}
MLR;
propo(u, lo, hi);
if (s <= mid) {
incre(s, e, x, lc, lo, mid);
}
if (e > mid) {
incre(s, e, x, rc, mid + 1, hi);
}
sm[u] = sm[lc] + sm[rc];
}
ll qsm(int s, int e, int u = 1, int lo = 1, int hi = n) {
if (lo >= s && hi <= e) {
return sm[u];
}
MLR;
propo(u, lo, hi);
ll res = 0;
if (s <= mid) {
res += qsm(s, e, lc, lo, mid);
}
if (e > mid) {
res += qsm(s, e, rc, mid + 1, hi);
}
return res;
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> n >> d;
REP (i, 1, n + 1) {
cin >> c[i];
}
cin >> q;
REP (i, 0, q) {
int l, r; cin >> l >> r;
rl[r].pb({l, i});
}
REP (i, 1, n + 1) {
while (!stk.empty() && stk.back().rc > c[i]) {
auto [l, r, lc, rc] = stk.back(); stk.pop_back();
ll w = (rc - c[i] - 1 + d) / d;
// lc - w * d >= stk.back().rc
// w <= (lc - stk.back().rc) / d
if (!stk.empty()) {
mnto(w, (lc - stk.back().rc) / d);
}
lc -= w * d; rc -= w * d;
incre(l, r, w);
if (!stk.empty() && lc - stk.back().rc < d) {
l = stk.back().l; lc = stk.back().lc;
stk.pop_back();
}
stk.pb({l, r, lc, rc});
}
stk.pb({i, i, c[i], c[i]});
for (auto [l, id] : rl[i]) {
ans[id] = qsm(l, i);
if (c[l] - qsm(l, l) * d < 0) {
ans[id] = -1;
}
}
}
REP (i, 0, q) {
cout << ans[i] << '\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'void propo(int, int, int)':
Main.cpp:53:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Main.cpp:63:5: note: in expansion of macro 'MLR'
63 | MLR;
| ^~~
Main.cpp: In function 'void incre(int, int, ll, int, int, int)':
Main.cpp:53:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Main.cpp:73:5: note: in expansion of macro 'MLR'
73 | MLR;
| ^~~
Main.cpp: In function 'll qsm(int, int, int, int, int)':
Main.cpp:53:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Main.cpp:87:5: note: in expansion of macro 'MLR'
87 | MLR;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
12632 KB |
Output is correct |
4 |
Correct |
5 ms |
12888 KB |
Output is correct |
5 |
Correct |
6 ms |
12892 KB |
Output is correct |
6 |
Correct |
5 ms |
12912 KB |
Output is correct |
7 |
Correct |
5 ms |
12892 KB |
Output is correct |
8 |
Correct |
6 ms |
12892 KB |
Output is correct |
9 |
Correct |
5 ms |
12892 KB |
Output is correct |
10 |
Correct |
5 ms |
12888 KB |
Output is correct |
11 |
Correct |
5 ms |
12892 KB |
Output is correct |
12 |
Correct |
4 ms |
10856 KB |
Output is correct |
13 |
Correct |
5 ms |
10844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
345 ms |
47112 KB |
Output is correct |
2 |
Correct |
283 ms |
34444 KB |
Output is correct |
3 |
Correct |
129 ms |
20248 KB |
Output is correct |
4 |
Correct |
362 ms |
41196 KB |
Output is correct |
5 |
Correct |
346 ms |
41016 KB |
Output is correct |
6 |
Correct |
311 ms |
36260 KB |
Output is correct |
7 |
Correct |
279 ms |
36244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
22168 KB |
Output is correct |
2 |
Correct |
381 ms |
48788 KB |
Output is correct |
3 |
Correct |
391 ms |
48724 KB |
Output is correct |
4 |
Correct |
417 ms |
48892 KB |
Output is correct |
5 |
Correct |
397 ms |
48916 KB |
Output is correct |
6 |
Correct |
337 ms |
43204 KB |
Output is correct |
7 |
Correct |
341 ms |
42956 KB |
Output is correct |
8 |
Correct |
344 ms |
46356 KB |
Output is correct |
9 |
Correct |
374 ms |
46532 KB |
Output is correct |
10 |
Correct |
266 ms |
40452 KB |
Output is correct |
11 |
Correct |
270 ms |
39304 KB |
Output is correct |
12 |
Correct |
330 ms |
52044 KB |
Output is correct |
13 |
Correct |
343 ms |
52968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
305 ms |
32100 KB |
Output is correct |
2 |
Correct |
398 ms |
40648 KB |
Output is correct |
3 |
Correct |
226 ms |
24992 KB |
Output is correct |
4 |
Correct |
386 ms |
43864 KB |
Output is correct |
5 |
Correct |
423 ms |
47648 KB |
Output is correct |
6 |
Correct |
481 ms |
48612 KB |
Output is correct |
7 |
Correct |
390 ms |
39372 KB |
Output is correct |
8 |
Correct |
434 ms |
48580 KB |
Output is correct |
9 |
Correct |
415 ms |
39964 KB |
Output is correct |
10 |
Correct |
354 ms |
39808 KB |
Output is correct |
11 |
Correct |
397 ms |
43904 KB |
Output is correct |
12 |
Correct |
439 ms |
43100 KB |
Output is correct |
13 |
Correct |
482 ms |
48368 KB |
Output is correct |
14 |
Correct |
418 ms |
44128 KB |
Output is correct |
15 |
Correct |
483 ms |
49320 KB |
Output is correct |
16 |
Correct |
456 ms |
44280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
12632 KB |
Output is correct |
4 |
Correct |
5 ms |
12888 KB |
Output is correct |
5 |
Correct |
6 ms |
12892 KB |
Output is correct |
6 |
Correct |
5 ms |
12912 KB |
Output is correct |
7 |
Correct |
5 ms |
12892 KB |
Output is correct |
8 |
Correct |
6 ms |
12892 KB |
Output is correct |
9 |
Correct |
5 ms |
12892 KB |
Output is correct |
10 |
Correct |
5 ms |
12888 KB |
Output is correct |
11 |
Correct |
5 ms |
12892 KB |
Output is correct |
12 |
Correct |
4 ms |
10856 KB |
Output is correct |
13 |
Correct |
5 ms |
10844 KB |
Output is correct |
14 |
Correct |
345 ms |
47112 KB |
Output is correct |
15 |
Correct |
283 ms |
34444 KB |
Output is correct |
16 |
Correct |
129 ms |
20248 KB |
Output is correct |
17 |
Correct |
362 ms |
41196 KB |
Output is correct |
18 |
Correct |
346 ms |
41016 KB |
Output is correct |
19 |
Correct |
311 ms |
36260 KB |
Output is correct |
20 |
Correct |
279 ms |
36244 KB |
Output is correct |
21 |
Correct |
133 ms |
22168 KB |
Output is correct |
22 |
Correct |
381 ms |
48788 KB |
Output is correct |
23 |
Correct |
391 ms |
48724 KB |
Output is correct |
24 |
Correct |
417 ms |
48892 KB |
Output is correct |
25 |
Correct |
397 ms |
48916 KB |
Output is correct |
26 |
Correct |
337 ms |
43204 KB |
Output is correct |
27 |
Correct |
341 ms |
42956 KB |
Output is correct |
28 |
Correct |
344 ms |
46356 KB |
Output is correct |
29 |
Correct |
374 ms |
46532 KB |
Output is correct |
30 |
Correct |
266 ms |
40452 KB |
Output is correct |
31 |
Correct |
270 ms |
39304 KB |
Output is correct |
32 |
Correct |
330 ms |
52044 KB |
Output is correct |
33 |
Correct |
343 ms |
52968 KB |
Output is correct |
34 |
Correct |
305 ms |
32100 KB |
Output is correct |
35 |
Correct |
398 ms |
40648 KB |
Output is correct |
36 |
Correct |
226 ms |
24992 KB |
Output is correct |
37 |
Correct |
386 ms |
43864 KB |
Output is correct |
38 |
Correct |
423 ms |
47648 KB |
Output is correct |
39 |
Correct |
481 ms |
48612 KB |
Output is correct |
40 |
Correct |
390 ms |
39372 KB |
Output is correct |
41 |
Correct |
434 ms |
48580 KB |
Output is correct |
42 |
Correct |
415 ms |
39964 KB |
Output is correct |
43 |
Correct |
354 ms |
39808 KB |
Output is correct |
44 |
Correct |
397 ms |
43904 KB |
Output is correct |
45 |
Correct |
439 ms |
43100 KB |
Output is correct |
46 |
Correct |
482 ms |
48368 KB |
Output is correct |
47 |
Correct |
418 ms |
44128 KB |
Output is correct |
48 |
Correct |
483 ms |
49320 KB |
Output is correct |
49 |
Correct |
456 ms |
44280 KB |
Output is correct |
50 |
Correct |
467 ms |
49704 KB |
Output is correct |
51 |
Correct |
352 ms |
43236 KB |
Output is correct |
52 |
Correct |
362 ms |
46320 KB |
Output is correct |
53 |
Correct |
302 ms |
39372 KB |
Output is correct |
54 |
Correct |
343 ms |
52912 KB |
Output is correct |
55 |
Correct |
395 ms |
48644 KB |
Output is correct |
56 |
Correct |
389 ms |
44368 KB |
Output is correct |
57 |
Correct |
361 ms |
41044 KB |
Output is correct |
58 |
Correct |
413 ms |
42200 KB |
Output is correct |
59 |
Correct |
399 ms |
47556 KB |
Output is correct |
60 |
Correct |
377 ms |
44368 KB |
Output is correct |
61 |
Correct |
268 ms |
39340 KB |
Output is correct |
62 |
Correct |
256 ms |
40052 KB |
Output is correct |
63 |
Correct |
335 ms |
51552 KB |
Output is correct |
64 |
Correct |
395 ms |
43960 KB |
Output is correct |