oj.uz

Submission #1117898

# Submission time Handle Problem Language Result Execution time Memory
1117898 2024-11-24T09:34:14 Z XRomanticCatX Triple Jump (JOI19_jumps) C++17
0 / 100
 249 ms 72700 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long int
#define pii pair<int , int>
#define f first
#define s second

const int MAXN = 1e6 + 5;

const int MOD = (119 >> 23) ^ 1;

const int INF = 1e10;

int p = 1;

struct segment{
	int val[MAXN * 2];
	int seg[MAXN * 2];
	int lazy[MAXN * 2];
	segment(){
		for(int i = 1 ; i < MAXN * 2 ; i++){
			val[i] = 0;
			seg[i] = 0;
			lazy[i] = 0;
		}
	}
	void build(){
		for(int i = p - 1 ; i >= 1 ; i--){
			val[i] = max(val[i * 2] , val[i * 2 + 1]);
		}
	}
	int getmax(int v , int vl , int vr , int l , int r){
		if(vr < l || r < vl) return 0;
		if(vl >= l && vr <= r) return val[v];
		int mid = (vr + vl) >> 1;
		return max(getmax(v * 2 , vl , mid , l , r) , getmax(v * 2 + 1 , mid + 1 , vr , l , r));
	}
	void shift(int v){
		if(v >= p) return;
		lazy[v * 2] = max(lazy[v * 2] , lazy[v]);
		lazy[v * 2 + 1] = max(lazy[v * 2 + 1] , lazy[v]);
		seg[v * 2] = max(seg[v * 2] , lazy[v] + val[v * 2]);
		seg[v * 2 + 1] = max(seg[v * 2 + 1] , lazy[v] + val[v * 2 + 1]);
		lazy[v] = 0;
	}
	void update(int v , int vl , int vr , int l , int r , int x){
		if(vr < l || r < vl) return;
		if(vl >= l && vr <= r){
			lazy[v] = max(lazy[v] , x);
			seg[v] = max(seg[v] , x + val[v]);
			return;
		}
		shift(v);
		int mid = (vr + vl) >> 1;
		update(v * 2 , vl , mid , l , r , x);
		update(v * 2 + 1 , mid + 1 , vr , l , r , x);
		seg[v] = max(seg[v * 2] , seg[v * 2 + 1]); 
	}
	int getans(int v , int vl , int vr , int l , int r){
		if(vr < l || r < vl) return 0;
		if(vl >= l && vr <= r) return seg[v];
		shift(v);
		int mid = (vr + vl) >> 1;
		return max(getans(v * 2 , vl , mid , l , r) , getans(v * 2 + 1 , mid + 1 , vr , l , r));
	}
};

segment tree;

signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0) ,cout.tie(0);
	int n;
	cin>>n;
	while(p < n) p *= 2;
	int a[n + 5];
	for(int i = 1 ; i <= n ; i++){
		cin>>a[i];
		tree.val[i + p] = a[i];
	}
	tree.build();
	int lef[n + 5];
	int rig[n + 5];
	stack <pii> st;
	st.push({INF , 0});
	for(int i = 1 ; i <= n ; i++){
		while(!st.empty() and a[i] >= st.top().f){
			st.pop();
		}
		lef[i] = st.top().s;
		st.push({a[i] , i});
	}
	stack <pii> stt;
	stt.push({INF , n + 1});
	for(int i = n ; i >= 1 ; i--){
		while(!stt.empty() and a[i] >= stt.top().f){
			stt.pop();
		}
		rig[i] = stt.top().s;
		stt.push({a[i] , i});
	}
	vector <int> update[n + 5];
	vector <pii> query[n + 5];
	for(int i = n ; i >= 1 ; i--){
		if(lef[i]) update[lef[i]].push_back(i);
		if(rig[i] <= n) update[i].push_back(rig[i]); 
	}	
	int q;
	cin>>q;
	int fq = q;
	while(q--){
		int l , r;
		cin>>l>>r;
		query[l].push_back({r , fq - q});
	}
	int ans[fq + 5];
	for(int i = n - 1 ; i >= 1 ; i--){
		for(auto u : update[i]){
			int C = tree.getmax(1 , 0 , p - 1 , u + u - i , n);
			tree.update(1 , 0 , p - 1 , u + u - i , n , a[i] + a[u]);
		}
		for(auto u : query[i]){
			ans[u.s] = tree.getans(1 , 0 , p - 1 , i , u.f);
		}
	}
	for(int i = 1 ; i <= fq ; i++){
		cout<<ans[i]<<endl;
	}
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:120:8: warning: unused variable 'C' [-Wunused-variable]
  120 |    int C = tree.getmax(1 , 0 , p - 1 , u + u - i , n);
      |        ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 70472 KB Output is correct
2 Correct 186 ms 72640 KB Output is correct
3 Correct 157 ms 72700 KB Output is correct
4 Correct 249 ms 70732 KB Output is correct
5 Incorrect 227 ms 70728 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

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