oj.uz

Submission #993676

# Submission time Handle Problem Language Result Execution time Memory
993676 2024-06-06T10:03:57 Z cpptowin Triple Jump (JOI19_jumps) C++17
100 / 100
 920 ms 138600 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
int n, a[maxn], l[maxn], r[maxn], q;
struct node
{
	int maxx, val, lazy;
} st[4 * maxn];
void build(int id, int l, int r)
{
	if (l == r)
	{
		st[id].maxx = st[id].val = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	st[id].maxx = st[id].val = max(st[id << 1].val, st[id << 1 | 1].val);
}
void down(int id)
{
	if (st[id].lazy == 0)
		return;
	maximize(st[id << 1].lazy, st[id].lazy);
	maximize(st[id << 1].maxx, st[id << 1].val + st[id].lazy);
	maximize(st[id << 1 | 1].lazy, st[id].lazy);
	maximize(st[id << 1 | 1].maxx, st[id << 1 | 1].val + st[id].lazy);
	st[id].lazy = 0;
}
void up(int id, int l, int r, int u, int v, int val)
{
	if (l > v or r < u)
		return;
	if (u <= l and r <= v)
	{
		maximize(st[id].lazy, val);
		maximize(st[id].maxx, st[id].val + val);
		return;
	}
	down(id);
	int mid = l + r >> 1;
	up(id << 1, l, mid, u, v, val);
	up(id << 1 | 1, mid + 1, r, u, v, val);
	st[id].maxx = max(st[id << 1].maxx, st[id << 1 | 1].maxx);
}
int get(int id, int l, int r, int u, int v)
{
	if (l > v or r < u)
		return 0;
	if (u <= l and r <= v)
		return st[id].maxx;
	down(id);
	int mid = l + r >> 1;
	return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
void L(int a[], int n, int ans[])
{
	stack<int> st;
	fo(i, 1, n)
	{
		while (st.size() and a[st.top()] < a[i])
			st.pop();
		ans[i] = (st.empty() ? 0 : st.top());
		st.push(i);
	}
}
void R(int a[], int n, int ans[])
{
	stack<int> st;
	fod(i, n, 1)
	{
		while (st.size() and a[st.top()] < a[i])
			st.pop();
		ans[i] = (st.empty() ? n + 1 : st.top());
		st.push(i);
	}
}
vi ke[maxn];
int res[maxn];
vii qry[maxn];
main()
{
#define name "TASK"
	if (fopen(name ".inp", "r"))
	{
		freopen(name ".inp", "r", stdin);
		freopen(name ".out", "w", stdout);
	}
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	fo(i, 1, n) cin >> a[i];
	build(1, 1, n);
	L(a, n, l);
	R(a, n, r);
	fo(i, 1, n)
	{
		if (r[i] != n + 1)
			ke[i].pb(r[i]);
		if (l[i] != 0)
			ke[l[i]].pb(i);
	}
	cin >> q;
	fo(i, 1, q)
	{
		int l, r;
		cin >> l >> r;
		qry[l].pb(r, i);
	}
	fod(i, n - 2, 1)
	{
		for (int j : ke[i])
		{
			int k = 2 * j - i;
			if (k <= n)
				up(1, 1, n, k, n, a[i] + a[j]);
		}
		for (auto [j, id] : qry[i])
		{
			res[id] = get(1, 1, n, i + 2, j);
		}
	}
	fo(i, 1, q) cout << res[i] << "\n";
}

Compilation message

jumps.cpp: In function 'void build(long long int, long long int, long long int)':
jumps.cpp:54:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |  int mid = l + r >> 1;
      |            ~~^~~
jumps.cpp: In function 'void up(long long int, long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:80:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |  int mid = l + r >> 1;
      |            ~~^~~
jumps.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:92:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |  int mid = l + r >> 1;
      |            ~~^~~
jumps.cpp: At global scope:
jumps.cpp:120:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  120 | main()
      | ^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:125:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |   freopen(name ".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:126:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |   freopen(name ".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47192 KB Output is correct
2 Correct 19 ms 47448 KB Output is correct
3 Correct 18 ms 47448 KB Output is correct
4 Correct 21 ms 47436 KB Output is correct
5 Correct 28 ms 47452 KB Output is correct
6 Correct 19 ms 47452 KB Output is correct
7 Correct 19 ms 47452 KB Output is correct
8 Correct 20 ms 47416 KB Output is correct
9 Correct 19 ms 47452 KB Output is correct
10 Correct 18 ms 47452 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47192 KB Output is correct
2 Correct 19 ms 47448 KB Output is correct
3 Correct 18 ms 47448 KB Output is correct
4 Correct 21 ms 47436 KB Output is correct
5 Correct 28 ms 47452 KB Output is correct
6 Correct 19 ms 47452 KB Output is correct
7 Correct 19 ms 47452 KB Output is correct
8 Correct 20 ms 47416 KB Output is correct
9 Correct 19 ms 47452 KB Output is correct
10 Correct 18 ms 47452 KB Output is correct
11 Correct 223 ms 75088 KB Output is correct
12 Correct 241 ms 74836 KB Output is correct
13 Correct 215 ms 75092 KB Output is correct
14 Correct 259 ms 74928 KB Output is correct
15 Correct 247 ms 74996 KB Output is correct
16 Correct 254 ms 74564 KB Output is correct
17 Correct 239 ms 74372 KB Output is correct
18 Correct 241 ms 74320 KB Output is correct
19 Correct 231 ms 75092 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 73556 KB Output is correct
2 Correct 80 ms 72304 KB Output is correct
3 Correct 79 ms 72256 KB Output is correct
4 Correct 132 ms 73616 KB Output is correct
5 Correct 130 ms 73552 KB Output is correct
6 Correct 139 ms 73008 KB Output is correct
7 Correct 123 ms 72788 KB Output is correct
8 Correct 131 ms 72908 KB Output is correct
9 Correct 125 ms 73040 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47192 KB Output is correct
2 Correct 19 ms 47448 KB Output is correct
3 Correct 18 ms 47448 KB Output is correct
4 Correct 21 ms 47436 KB Output is correct
5 Correct 28 ms 47452 KB Output is correct
6 Correct 19 ms 47452 KB Output is correct
7 Correct 19 ms 47452 KB Output is correct
8 Correct 20 ms 47416 KB Output is correct
9 Correct 19 ms 47452 KB Output is correct
10 Correct 18 ms 47452 KB Output is correct
11 Correct 223 ms 75088 KB Output is correct
12 Correct 241 ms 74836 KB Output is correct
13 Correct 215 ms 75092 KB Output is correct
14 Correct 259 ms 74928 KB Output is correct
15 Correct 247 ms 74996 KB Output is correct
16 Correct 254 ms 74564 KB Output is correct
17 Correct 239 ms 74372 KB Output is correct
18 Correct 241 ms 74320 KB Output is correct
19 Correct 231 ms 75092 KB Output is correct
20 Correct 130 ms 73556 KB Output is correct
21 Correct 80 ms 72304 KB Output is correct
22 Correct 79 ms 72256 KB Output is correct
23 Correct 132 ms 73616 KB Output is correct
24 Correct 130 ms 73552 KB Output is correct
25 Correct 139 ms 73008 KB Output is correct
26 Correct 123 ms 72788 KB Output is correct
27 Correct 131 ms 72908 KB Output is correct
28 Correct 125 ms 73040 KB Output is correct
29 Correct 920 ms 135316 KB Output is correct
30 Correct 775 ms 132296 KB Output is correct
31 Correct 751 ms 132248 KB Output is correct
32 Correct 874 ms 135452 KB Output is correct
33 Correct 912 ms 135336 KB Output is correct
34 Correct 885 ms 133192 KB Output is correct
35 Correct 852 ms 132684 KB Output is correct
36 Correct 869 ms 132688 KB Output is correct
37 Correct 862 ms 134272 KB Output is correct
38 Correct 549 ms 138060 KB Output is correct
39 Correct 548 ms 138120 KB Output is correct
40 Correct 536 ms 134992 KB Output is correct
41 Correct 525 ms 134180 KB Output is correct
42 Correct 630 ms 134228 KB Output is correct
43 Correct 527 ms 136008 KB Output is correct
44 Correct 570 ms 138208 KB Output is correct
45 Correct 581 ms 138324 KB Output is correct
46 Correct 578 ms 135136 KB Output is correct
47 Correct 567 ms 134616 KB Output is correct
48 Correct 570 ms 134740 KB Output is correct
49 Correct 609 ms 136784 KB Output is correct
50 Correct 645 ms 138404 KB Output is correct
51 Correct 653 ms 138600 KB Output is correct
52 Correct 633 ms 136096 KB Output is correct
53 Correct 691 ms 135764 KB Output is correct
54 Correct 631 ms 135692 KB Output is correct
55 Correct 636 ms 137296 KB Output is correct