oj.uz

답안 #191498

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
191498 2020-01-15T02:56:28 Z oolimry 3단 점프 (JOI19_jumps) C++14
0 / 100
 3 ms 504 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> ii;
const int inf = 1000000003;

struct node{
	int c;
	int ab;
	int abc;
};

const int N = 1 << 3;
static node tree[2*N+5];
static int arr[N+5];

node relax(node x, node y){
	node z;
	z.c = max(x.c, y.c);
	z.ab = max(x.ab, y.ab);
	z.abc = max(x.ab + y.c, max(x.abc,y.abc));
	return z;
}

void init(){
	for(int i = N;i < 2*N;i++){
		tree[i] = {arr[i-N],-inf,-inf};
	}
	for(int i = N-1;i > 0;i--){
		tree[i] = relax(tree[i<<1],tree[i<<1|1]);
	}
}

void update(int i, int v){
	i += N;
	tree[i].ab = max(tree[i].ab,v);
	tree[i].abc = max(tree[i].abc,tree[i].ab+tree[i].c);
	while(i > 1){
		i >>= 1;
		tree[i] = relax(tree[i<<1],tree[i<<1|1]);
	}
}

int query(int l, int r){
	node L = {-inf,-inf,-inf};
	node R = {-inf,-inf,-inf};
	for(l += N, r += N;l < r;l >>= 1, r >>= 1){
		if(l&1){
			L = relax(L,tree[l]); 
			l++;
		}
		if(r&1){
			r--;
			R = relax(tree[r],R);
		}
	}
	return relax(L,R).abc;
}

int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n; 
	for(int i = 0;i < n;i++) cin >> arr[i];
	
	vector<int> critical[n];
	vector<ii> queries[n];
	stack<int> s;
	for(int b = 0;b < n;b++){
		while(!s.empty() && arr[b] >= arr[s.top()]){
			int a = s.top();
			int c = 2 * b - a;
			if(c < n) critical[a].push_back(c);
			s.pop();
		}
		if(!s.empty()){
			int a = s.top();
			int c = 2 * b - a;
			if(c < n) critical[a].push_back(c);
		}
		s.push(b);
	}
	
	int q; cin >> q;
	int answer[q];
	for(int i = 0;i < q;i++){
		int l, r; cin >> l >> r;
		queries[l-1].push_back(ii(r-1,i));
	}
	
	init();
	
	for(int l = n-1;l >= 0;l--){
		int a = l;
		for(int ab : critical[a]){
			int b = (a + ab) / 2;
			update(ab, arr[a] + arr[b]);
		}
		for(ii Q : queries[l]){
			int r = Q.first;
			answer[Q.second] = query(l, r+1);
		}
	}
	
	for(int i = 0;i < q;i++) cout << answer[i] << "\n";
	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -