oj.uz

Submission #950420

# Submission time Handle Problem Language Result Execution time Memory
950420 2024-03-20T09:38:43 Z vjudge1 Triple Jump (JOI19_jumps) C++17
100 / 100
 856 ms 139356 KB 
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#include<bits/stdc++.h>	

using namespace std;

#define all(a) a.begin(), a.end()                                                   
#define rall(a) a.rbegin(), a.rend()                 
#define sz(a) (int)a.size()
#define s second
#define f first
 
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
     
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
 
const int N = 5e5 + 1, mod = 1e9 + 7;

const ll inf = 1e9;
 
double eps = 1e-15;
                                                
bool flg = 0;

array<int, 4> t[4 * N]; 
int add[4 * N], a[N], n;

void push(int u, int tl, int tr) {
	if (!add[u]) return;
	t[u][0] = t[u][3] = add[u];
	t[u][2] = t[u][1] + t[u][0];
	if (tl < tr) {
		add[u * 2] = add[u];
		add[u * 2 + 1] = add[u];
	}
	add[u] = 0;
}

void bld(int u = 1, int tl = 1, int tr = n) {
    if (tl == tr) {
		t[u][1] = a[tl];
		return;
    }
    int m = (tl + tr) / 2;
    bld(u * 2, tl, m);
    bld(u * 2 + 1, m + 1, tr);
    t[u][1] = max(t[u * 2][1], t[u * 2 + 1][1]);
}	

void upt(int l, int r, int v, int u = 1, int tl = 1, int tr = n) {
    push(u, tl, tr);
    if (tl > r || tr < l || t[u][3] >= v) return;
    if (tl >= l && tr <= r && t[u][0] <= v) {
    	add[u] = v;
    	push(u, tl, tr);
    	return;
    }
    int m = (tl + tr) / 2;
    upt(l, r, v, u * 2, tl, m);
    upt(l, r, v, u * 2 + 1, m + 1, tr);
	t[u][0] = max(t[u * 2][0], t[u * 2 + 1][0]);
	t[u][3] = min(t[u * 2][3], t[u * 2 + 1][3]);
	t[u][2] = max(t[u * 2][2], t[u * 2 + 1][2]);
}

int get(int l, int r, int u = 1, int tl = 1, int tr = n) {
	push(u, tl, tr);
	if (tl > r || tr < l) return 0;
	if (tl >= l && tr <= r) return t[u][2];
	int m = (tl + tr) / 2;
	return max(get(l, r, u * 2, tl, m), get(l, r, u * 2 + 1, m + 1, tr));
}	

void slv() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	bld();
	int q;
	cin >> q;
	vector<pii> qr[n + 1];
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		qr[l].push_back({r, i});
	}
	vector<pii> h[4 * n];
	stack<int> s;
	for (int i = n; i >= 1; i--) {
		while (sz(s) && a[s.top()] < a[i]) s.pop();
		if (sz(s)) {
		    int x = s.top() - i;
		    if (s.top() + x <= n) {
		    	h[i].push_back({s.top() + x, a[i] + a[s.top()]});
		    }
		}
		s.push(i);	                      	
	}
	while (sz(s)) s.pop();
	for (int i = 1; i <= n; i++) {
	 	while (sz(s) && a[s.top()] < a[i]) s.pop();
	 	if (sz(s)) {
	 		int x = i - s.top();
	 		if (i + x <= n) {
	 			h[s.top()].push_back({i + x, a[i] + a[s.top()]});	
	 		}
	 	}
	 	s.push(i); 
	}
	int ans[q + 1];
	for (int i = n; i >= 1; i--) {
		for (auto [r, v]: h[i]) upt(r, n, v);
		for (auto [r, id]: qr[i]) ans[id] = get(i + 2, r);	
	}	
	cout << '\n';
	for (int i = 1; i <= q; i++) cout << ans[i] << ' ';
}                                                                           
 
main() {
	//freopen("rsq.in", "r", stdin);                                                                                     
	//freopen("rsq.out", "w", stdout);                                                                                     
	ios_base::sync_with_stdio(0);	                                                                                       
	cin.tie(0);
	int tp = 1;
	if (flg) cin >> tp;
	while (tp--) {  	
		slv();
	}
}
//wenomechainsama

Compilation message

jumps.cpp:124:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  124 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2508 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2508 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 195 ms 21588 KB Output is correct
12 Correct 208 ms 21824 KB Output is correct
13 Correct 199 ms 21744 KB Output is correct
14 Correct 201 ms 21820 KB Output is correct
15 Correct 188 ms 21588 KB Output is correct
16 Correct 207 ms 21140 KB Output is correct
17 Correct 193 ms 21008 KB Output is correct
18 Correct 202 ms 21340 KB Output is correct
19 Correct 188 ms 21576 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 48976 KB Output is correct
2 Correct 87 ms 46672 KB Output is correct
3 Correct 91 ms 46932 KB Output is correct
4 Correct 161 ms 48724 KB Output is correct
5 Correct 159 ms 48700 KB Output is correct
6 Correct 147 ms 47952 KB Output is correct
7 Correct 149 ms 47856 KB Output is correct
8 Correct 151 ms 48316 KB Output is correct
9 Correct 172 ms 48300 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2508 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 195 ms 21588 KB Output is correct
12 Correct 208 ms 21824 KB Output is correct
13 Correct 199 ms 21744 KB Output is correct
14 Correct 201 ms 21820 KB Output is correct
15 Correct 188 ms 21588 KB Output is correct
16 Correct 207 ms 21140 KB Output is correct
17 Correct 193 ms 21008 KB Output is correct
18 Correct 202 ms 21340 KB Output is correct
19 Correct 188 ms 21576 KB Output is correct
20 Correct 152 ms 48976 KB Output is correct
21 Correct 87 ms 46672 KB Output is correct
22 Correct 91 ms 46932 KB Output is correct
23 Correct 161 ms 48724 KB Output is correct
24 Correct 159 ms 48700 KB Output is correct
25 Correct 147 ms 47952 KB Output is correct
26 Correct 149 ms 47856 KB Output is correct
27 Correct 151 ms 48316 KB Output is correct
28 Correct 172 ms 48300 KB Output is correct
29 Correct 844 ms 133672 KB Output is correct
30 Correct 665 ms 128728 KB Output is correct
31 Correct 712 ms 129140 KB Output is correct
32 Correct 837 ms 133500 KB Output is correct
33 Correct 856 ms 133796 KB Output is correct
34 Correct 825 ms 131440 KB Output is correct
35 Correct 806 ms 131116 KB Output is correct
36 Correct 842 ms 130828 KB Output is correct
37 Correct 830 ms 132480 KB Output is correct
38 Correct 621 ms 139356 KB Output is correct
39 Correct 616 ms 139048 KB Output is correct
40 Correct 617 ms 135896 KB Output is correct
41 Correct 601 ms 135356 KB Output is correct
42 Correct 609 ms 135512 KB Output is correct
43 Correct 621 ms 137288 KB Output is correct
44 Correct 650 ms 138452 KB Output is correct
45 Correct 641 ms 138444 KB Output is correct
46 Correct 647 ms 135336 KB Output is correct
47 Correct 629 ms 135064 KB Output is correct
48 Correct 639 ms 134992 KB Output is correct
49 Correct 650 ms 137200 KB Output is correct
50 Correct 711 ms 136532 KB Output is correct
51 Correct 742 ms 136672 KB Output is correct
52 Correct 731 ms 134112 KB Output is correct
53 Correct 698 ms 133548 KB Output is correct
54 Correct 691 ms 133716 KB Output is correct
55 Correct 708 ms 135444 KB Output is correct