oj.uz

Submission #555990

# Submission time Handle Problem Language Result Execution time Memory
555990 2022-05-02T06:32:11 Z SavicS Triple Jump (JOI19_jumps) C++17
100 / 100
 1142 ms 74160 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
 
#define ff(i,a,b) for(int i = a; i <= b; i++)
#define fb(i,b,a) for(int i = b; i >= a; i--)
#define trav(a,x) for (auto& a : x)
 
#define sz(a) (int)(a).size()
#define pb push_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

const int mod = 1000000007;
const int inf = 1e9 + 5;
const int mxN = 500005; 

int n, q;
int niz[mxN];

vector<pii> upit[mxN];
ll res[mxN];

ll bor[4 * mxN][2]; // 1 - max update, 0 - max vrednost 
ll lenj[4 * mxN];
void build(int v, int tl, int tr){
	if(tl == tr){
		bor[v][0] = bor[v][1] = niz[tl];
		return;
	}
	int mid = (tl + tr) / 2;
	build(v * 2, tl, mid); build(v * 2 + 1, mid + 1, tr);
	bor[v][0] = max(bor[v * 2][0], bor[v * 2 + 1][0]);
	bor[v][1] = max(bor[v * 2][1], bor[v * 2 + 1][1]);
}

void propagate(int v, int tl, int tr){
	if(lenj[v] != 0){
		bor[v][1] = max(bor[v][1], bor[v][0] + lenj[v]);
		if(tl != tr){
			lenj[v * 2] = max(lenj[v * 2], lenj[v]);
			lenj[v * 2 + 1] = max(lenj[v * 2 + 1], lenj[v]);
		}
		lenj[v] = 0;
	}
}

void lazyupd(int v, int tl, int tr, int l, int r, ll val){
	propagate(v, tl, tr); 
	if(tl > tr || l > tr || tl > r)return;
	if(tl >= l && tr <= r){
		lenj[v] = max(lenj[v], val);
		propagate(v, tl, tr);
		return;
	}
	int mid = (tl + tr) / 2;
	lazyupd(v * 2, tl, mid, l, r, val); lazyupd(v * 2 + 1, mid + 1, tr, l, r, val);
	bor[v][1] = max(bor[v * 2][1], bor[v * 2 + 1][1]);
}

ll kveri(int v, int tl, int tr, int l, int r){
	propagate(v, tl, tr);
	if(tl > r || l > tr)return 0;
	if(tl >= l && tr <= r)return bor[v][1];
	int mid = (tl + tr) / 2;
	return max(kveri(v * 2, tl, mid, l, r), kveri(v * 2 + 1, mid + 1, tr, l, r));
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    ff(i,1,n)cin >> niz[i];

    cin >> q;
    ff(i,1,q){
    	int l, r;
    	cin >> l >> r;
    	upit[l].pb({r,i});
    }

    stack<int> stek; build(1,1,n);
    fb(i,n,1){
    	
    	while(sz(stek) && niz[i] > niz[stek.top()]){
    		int j = stek.top(); stek.pop();
    		lazyupd(1,1,n,j + j - i,n,niz[i] + niz[j]);
    	}

    	if(sz(stek) != 0){
    		int j = stek.top();
    		lazyupd(1,1,n,j + j - i,n,niz[i] + niz[j]);
    	}

    	stek.push(i);

    	for(auto c : upit[i]){
    		int r = c.fi;
    		int id = c.se;
    		res[id] = kveri(1,1,n,i,r);
    	}

    }

    ff(i,1,q)cout << res[i] << '\n';

    return 0;
}
/*

3
1000000000 1000000000 1000000000
1
1 3

15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
12
1 15
3 12
11 14
1 13
5 9
4 6
6 14
2 5
4 15
1 7
1 10
8 13

5
5 4 4 5 4
1
1 5
 
5
5 2 1 5 3
3
1 4
2 5
1 5
 
// probati bojenje sahovski
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12092 KB Output is correct
3 Correct 6 ms 12092 KB Output is correct
4 Correct 6 ms 12088 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 7 ms 12092 KB Output is correct
7 Correct 9 ms 12116 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12092 KB Output is correct
3 Correct 6 ms 12092 KB Output is correct
4 Correct 6 ms 12088 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 7 ms 12092 KB Output is correct
7 Correct 9 ms 12116 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 276 ms 33060 KB Output is correct
12 Correct 289 ms 32960 KB Output is correct
13 Correct 340 ms 33036 KB Output is correct
14 Correct 269 ms 33064 KB Output is correct
15 Correct 326 ms 33144 KB Output is correct
16 Correct 300 ms 32408 KB Output is correct
17 Correct 294 ms 32388 KB Output is correct
18 Correct 304 ms 32452 KB Output is correct
19 Correct 304 ms 32988 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 26812 KB Output is correct
2 Correct 83 ms 27724 KB Output is correct
3 Correct 90 ms 26876 KB Output is correct
4 Correct 160 ms 26836 KB Output is correct
5 Correct 145 ms 26816 KB Output is correct
6 Correct 132 ms 26168 KB Output is correct
7 Correct 141 ms 26060 KB Output is correct
8 Correct 141 ms 26116 KB Output is correct
9 Correct 157 ms 26468 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12092 KB Output is correct
3 Correct 6 ms 12092 KB Output is correct
4 Correct 6 ms 12088 KB Output is correct
5 Correct 8 ms 12116 KB Output is correct
6 Correct 7 ms 12092 KB Output is correct
7 Correct 9 ms 12116 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 276 ms 33060 KB Output is correct
12 Correct 289 ms 32960 KB Output is correct
13 Correct 340 ms 33036 KB Output is correct
14 Correct 269 ms 33064 KB Output is correct
15 Correct 326 ms 33144 KB Output is correct
16 Correct 300 ms 32408 KB Output is correct
17 Correct 294 ms 32388 KB Output is correct
18 Correct 304 ms 32452 KB Output is correct
19 Correct 304 ms 32988 KB Output is correct
20 Correct 141 ms 26812 KB Output is correct
21 Correct 83 ms 27724 KB Output is correct
22 Correct 90 ms 26876 KB Output is correct
23 Correct 160 ms 26836 KB Output is correct
24 Correct 145 ms 26816 KB Output is correct
25 Correct 132 ms 26168 KB Output is correct
26 Correct 141 ms 26060 KB Output is correct
27 Correct 141 ms 26116 KB Output is correct
28 Correct 157 ms 26468 KB Output is correct
29 Correct 1064 ms 68456 KB Output is correct
30 Correct 938 ms 70580 KB Output is correct
31 Correct 887 ms 68408 KB Output is correct
32 Correct 1096 ms 68560 KB Output is correct
33 Correct 1062 ms 68436 KB Output is correct
34 Correct 1142 ms 66160 KB Output is correct
35 Correct 1069 ms 65828 KB Output is correct
36 Correct 1133 ms 65896 KB Output is correct
37 Correct 1094 ms 67400 KB Output is correct
38 Correct 705 ms 74056 KB Output is correct
39 Correct 767 ms 74160 KB Output is correct
40 Correct 711 ms 70728 KB Output is correct
41 Correct 739 ms 70260 KB Output is correct
42 Correct 676 ms 70348 KB Output is correct
43 Correct 726 ms 72080 KB Output is correct
44 Correct 740 ms 73500 KB Output is correct
45 Correct 757 ms 73624 KB Output is correct
46 Correct 739 ms 70468 KB Output is correct
47 Correct 759 ms 69888 KB Output is correct
48 Correct 752 ms 69920 KB Output is correct
49 Correct 756 ms 72192 KB Output is correct
50 Correct 863 ms 71696 KB Output is correct
51 Correct 818 ms 71564 KB Output is correct
52 Correct 850 ms 69128 KB Output is correct
53 Correct 890 ms 69040 KB Output is correct
54 Correct 817 ms 68748 KB Output is correct
55 Correct 780 ms 70628 KB Output is correct