oj.uz

Submission #915202

# Submission time Handle Problem Language Result Execution time Memory
915202 2024-01-23T13:23:49 Z qin Triple Jump (JOI19_jumps) C++17
27 / 100
 71 ms 5328 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
struct seg{
		vector<int> t;
		int base = 1;
		void init(int n, vector<int> &a){
				while(base < n) base <<= 1;
				t.resize(base<<1);
				for(int i = 1; i <= n; ++i) t[i+base-1] = a[i];
				for(int i = base-1; i; --i) t[i] = max(t[i<<1], t[i<<1|1]);
		}
		int query_max(int i, int s, int e, int x, int y){
				if(x <= s && e <= y) return t[i];
				int mid = (s+e)>>1, ret = 0;
				if(x <= mid) ret = max(ret, query_max(i<<1, s, mid, x, y));
				if(mid < y) ret = max(ret, query_max(i<<1|1, mid+1, e, x, y));
				return ret;
		}
		int query(int x, int y){
				if(x <= y) return query_max(1, 1, base, max(1, x), min(base, y));
				return 0;
		}
};
void answer(){
		int n; scanf("%d", &n);
		vector<int> t(n+1);
		for(int i = 1; i <= n; ++i) scanf("%d", &t[i]);
		seg seg; seg.init(n, t);
		int q; scanf("%d", &q);
		for(++q; --q; ){
				int l, r; scanf("%d%d", &l, &r);
				vector<int> st;
				for(int i = r; i > l; --i)
						if(st.empty() || t[st.back()] < t[i]) st.emplace_back(i);
				int mx_pos = l, result = 0;
				for(int i = l+1; i <= r-1; ++i){
						if(st.back() == i) st.pop_back();
						result = max(result, seg.query(max(l, i-(st.back()-i)), i-1)+t[i]+t[st.back()]);
						result = max(result, t[mx_pos]+t[i]+seg.query(i+(i-mx_pos), r));
						if(t[mx_pos] <= t[i]) mx_pos = i;
				}
				printf("%d\n", result);
		}
}
int main(){
		int T = 1;
		for(++T; --T; ) answer();
		return 0;
}

Compilation message

jumps.cpp: In function 'void answer()':
jumps.cpp:35:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   int n; scanf("%d", &n);
      |          ~~~~~^~~~~~~~~~
jumps.cpp:37:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   for(int i = 1; i <= n; ++i) scanf("%d", &t[i]);
      |                               ~~~~~^~~~~~~~~~~~~
jumps.cpp:39:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   int q; scanf("%d", &q);
      |          ~~~~~^~~~~~~~~~
jumps.cpp:41:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     int l, r; scanf("%d%d", &l, &r);
      |               ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4284 KB Output is correct
2 Correct 70 ms 4288 KB Output is correct
3 Correct 45 ms 5328 KB Output is correct
4 Correct 69 ms 4284 KB Output is correct
5 Correct 65 ms 4180 KB Output is correct
6 Correct 64 ms 4048 KB Output is correct
7 Correct 71 ms 3932 KB Output is correct
8 Correct 63 ms 4032 KB Output is correct
9 Correct 63 ms 4184 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -