oj.uz

Submission #991789

# Submission time Handle Problem Language Result Execution time Memory
991789 2024-06-03T07:15:37 Z CodePlatina Fish 3 (JOI24_fish3) C++17
100 / 100
 525 ms 52584 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define plll pair<long long, pll>
#define tiii array<int, 3>
#define tiiii array<int, 4>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
typedef long long ll;
const int INF = (int)1e9 + 7;

using namespace std;

vector<pii> qr[303030];

ll seg[1212121];
ll lazy[1212121];

void down(int ind, int s, int e, ll x)
{
	seg[ind] += x * (e - s);
	lazy[ind] += x;
}

void prop(int ind, int s, int e)
{
	if(lazy[ind])
	{
		int mid = s + e >> 1;
		down(ind << 1, s, mid, lazy[ind]);
		down(ind << 1 | 1, mid, e, lazy[ind]);
		lazy[ind] = 0;
	}
}

void upd(int ind, int s, int e, int l, int r, ll x)
{
	if(r <= s || e <= l) return;
	if(l <= s && e <= r)
	{
		down(ind, s, e, x);
		return;
	}

	prop(ind, s, e);
	int mid = s + e >> 1;
	upd(ind << 1, s, mid, l, r, x);
	upd(ind << 1 | 1, mid, e, l, r, x);
	seg[ind] = seg[ind << 1] + seg[ind << 1 | 1];
}

ll qry(int ind, int s, int e, int l, int r)
{
	if(r <= s || e <= l) return 0;
	if(l <= s && e <= r) return seg[ind];

	prop(ind, s, e);
	int mid = s + e >> 1;
	return qry(ind << 1, s, mid, l, r) + qry(ind << 1 | 1, mid, e, l, r);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n; ll d; cin >> n >> d;
	ll A[n]; for(auto &i : A) cin >> i;
	int T; cin >> T;
	for(int i = 0; i < T; ++i)
	{
		int l, r; cin >> l >> r; --l;
		qr[r].push_back({l, i});
	}

	ll ps[n + 1]; ps[0] = 0;
	for(int i = 0; i < n; ++i) ps[i + 1] = ps[i] + A[i];

	vector<int> V;
	ll ans[T];
	for(int r = 1; r <= n; ++r)
	{
		upd(1, 0, n, r - 1, r, A[r - 1]);
		V.push_back(r - 1);
		while(V.size() >= 2)
		{
			ll x = qry(1, 0, n, V.back() - 1, V.back());
			ll y = qry(1, 0, n, V.back(), V.back() + 1);
			if(x <= y) break;
			ll t = ((x - y - 1) / d + 1) * d;
			upd(1, 0, n, V[(int)V.size() - 2], V.back(), -t);
			V.pop_back();
		}
		for(auto [l, i] : qr[r])
		{
			if(qry(1, 0, n, l, l + 1) < 0) ans[i] = -1;
			else ans[i] = (ps[r] - ps[l] - qry(1, 0, n, l, r)) / d;
		}


		// for(int i = 0; i < n; ++i) cout << qry(1, 0, n, i, i + 1) << ' '; cout << endl;
	}

	for(int i = 0; i < T; ++i) cout << ans[i] << '\n';
}

Compilation message

Main.cpp: In function 'void prop(int, int, int)':
Main.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   int mid = s + e >> 1;
      |             ~~^~~
Main.cpp: In function 'void upd(int, int, int, int, int, ll)':
Main.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int mid = s + e >> 1;
      |            ~~^~~
Main.cpp: In function 'll qry(int, int, int, int, int)':
Main.cpp:61:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |  int mid = s + e >> 1;
      |            ~~^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9912 KB Output is correct
4 Correct 5 ms 10076 KB Output is correct
5 Correct 4 ms 10180 KB Output is correct
6 Correct 5 ms 9968 KB Output is correct
7 Correct 4 ms 9964 KB Output is correct
8 Correct 5 ms 10076 KB Output is correct
9 Correct 4 ms 10076 KB Output is correct
10 Correct 5 ms 10076 KB Output is correct
11 Correct 4 ms 10076 KB Output is correct
12 Correct 4 ms 10076 KB Output is correct
13 Correct 4 ms 10076 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 44468 KB Output is correct
2 Correct 332 ms 44104 KB Output is correct
3 Correct 75 ms 19868 KB Output is correct
4 Correct 349 ms 44836 KB Output is correct
5 Correct 339 ms 44880 KB Output is correct
6 Correct 323 ms 43212 KB Output is correct
7 Correct 342 ms 43276 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 23380 KB Output is correct
2 Correct 462 ms 52564 KB Output is correct
3 Correct 427 ms 52584 KB Output is correct
4 Correct 445 ms 52460 KB Output is correct
5 Correct 432 ms 52560 KB Output is correct
6 Correct 428 ms 46100 KB Output is correct
7 Correct 446 ms 46160 KB Output is correct
8 Correct 442 ms 49488 KB Output is correct
9 Correct 456 ms 49412 KB Output is correct
10 Correct 329 ms 47208 KB Output is correct
11 Correct 376 ms 47304 KB Output is correct
12 Correct 462 ms 50380 KB Output is correct
13 Correct 408 ms 50380 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 36432 KB Output is correct
2 Correct 444 ms 45568 KB Output is correct
3 Correct 212 ms 27732 KB Output is correct
4 Correct 420 ms 48972 KB Output is correct
5 Correct 385 ms 51144 KB Output is correct
6 Correct 391 ms 52216 KB Output is correct
7 Correct 356 ms 41820 KB Output is correct
8 Correct 433 ms 52304 KB Output is correct
9 Correct 365 ms 44884 KB Output is correct
10 Correct 380 ms 44624 KB Output is correct
11 Correct 425 ms 48980 KB Output is correct
12 Correct 388 ms 48208 KB Output is correct
13 Correct 460 ms 52232 KB Output is correct
14 Correct 289 ms 48000 KB Output is correct
15 Correct 411 ms 52072 KB Output is correct
16 Correct 316 ms 47956 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9912 KB Output is correct
4 Correct 5 ms 10076 KB Output is correct
5 Correct 4 ms 10180 KB Output is correct
6 Correct 5 ms 9968 KB Output is correct
7 Correct 4 ms 9964 KB Output is correct
8 Correct 5 ms 10076 KB Output is correct
9 Correct 4 ms 10076 KB Output is correct
10 Correct 5 ms 10076 KB Output is correct
11 Correct 4 ms 10076 KB Output is correct
12 Correct 4 ms 10076 KB Output is correct
13 Correct 4 ms 10076 KB Output is correct
14 Correct 428 ms 44468 KB Output is correct
15 Correct 332 ms 44104 KB Output is correct
16 Correct 75 ms 19868 KB Output is correct
17 Correct 349 ms 44836 KB Output is correct
18 Correct 339 ms 44880 KB Output is correct
19 Correct 323 ms 43212 KB Output is correct
20 Correct 342 ms 43276 KB Output is correct
21 Correct 113 ms 23380 KB Output is correct
22 Correct 462 ms 52564 KB Output is correct
23 Correct 427 ms 52584 KB Output is correct
24 Correct 445 ms 52460 KB Output is correct
25 Correct 432 ms 52560 KB Output is correct
26 Correct 428 ms 46100 KB Output is correct
27 Correct 446 ms 46160 KB Output is correct
28 Correct 442 ms 49488 KB Output is correct
29 Correct 456 ms 49412 KB Output is correct
30 Correct 329 ms 47208 KB Output is correct
31 Correct 376 ms 47304 KB Output is correct
32 Correct 462 ms 50380 KB Output is correct
33 Correct 408 ms 50380 KB Output is correct
34 Correct 395 ms 36432 KB Output is correct
35 Correct 444 ms 45568 KB Output is correct
36 Correct 212 ms 27732 KB Output is correct
37 Correct 420 ms 48972 KB Output is correct
38 Correct 385 ms 51144 KB Output is correct
39 Correct 391 ms 52216 KB Output is correct
40 Correct 356 ms 41820 KB Output is correct
41 Correct 433 ms 52304 KB Output is correct
42 Correct 365 ms 44884 KB Output is correct
43 Correct 380 ms 44624 KB Output is correct
44 Correct 425 ms 48980 KB Output is correct
45 Correct 388 ms 48208 KB Output is correct
46 Correct 460 ms 52232 KB Output is correct
47 Correct 289 ms 48000 KB Output is correct
48 Correct 411 ms 52072 KB Output is correct
49 Correct 316 ms 47956 KB Output is correct
50 Correct 525 ms 52356 KB Output is correct
51 Correct 446 ms 46160 KB Output is correct
52 Correct 454 ms 49264 KB Output is correct
53 Correct 356 ms 47312 KB Output is correct
54 Correct 395 ms 50380 KB Output is correct
55 Correct 449 ms 52308 KB Output is correct
56 Correct 328 ms 47952 KB Output is correct
57 Correct 360 ms 44916 KB Output is correct
58 Correct 335 ms 44880 KB Output is correct
59 Correct 475 ms 50260 KB Output is correct
60 Correct 363 ms 48112 KB Output is correct
61 Correct 320 ms 47212 KB Output is correct
62 Correct 355 ms 47344 KB Output is correct
63 Correct 430 ms 50380 KB Output is correct
64 Correct 421 ms 46928 KB Output is correct