제출 #1009288

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009288		PoPularPlusPlus	3단 점프 (JOI19_jumps)	C++17	100 / 100	1004 ms	87940 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 1000000007;
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct Seg{
	vector<int> mx,ans;
	vector<int> lazy;
	int siz;

	void init(int n){
		siz = 1;
		while(siz < n)siz*=2;

		mx.assign(siz * 2 , 0);
		ans.assign(siz * 2 , 0);
		lazy.assign(siz * 2 , -1);
	}

	void push(int x){
		lazy[2 * x + 1] = max(lazy[2 * x + 1] , lazy[x]);
		lazy[2 * x + 2] = max(lazy[2 * x + 2] , lazy[x]);
		ans[2 * x + 1] = max(ans[2 * x + 1] , lazy[2 * x + 1] + mx[2 * x + 1]);
		ans[2 * x + 2] = max(ans[2 * x + 2] , lazy[2 * x + 2] + mx[2 * x + 2]);
		lazy[x] = -1;
	}

	void build(vector<int>& a , int x , int lx , int rx){
		if(rx - lx == 1){
			if(lx < a.size()){
				mx[x] = ans[x] = a[lx];
			}
			return;
		}
		int m = (lx + rx)/2;
		build(a , 2 * x + 1 ,lx , m);
		build(a , 2 * x + 2 , m , rx);
		mx[x] = max(mx[2 * x + 1] , mx[2 * x + 2]);
		ans[x] = max(ans[2 *x + 1] , ans[2 * x + 2]);
	}

	void build(vector<int>& a){
		build(a , 0 , 0 , siz);
	}

	void set(int l , int r, int val, int x , int lx, int rx){
		if(r <= lx || rx <= l)return;
		if(lx >= l && rx <= r){
			lazy[x] = max(lazy[x], val);
			ans[x] = max(ans[x] , mx[x] + val);
			return;
		}

		push(x);
		int m = (lx + rx)/2;
		set(l , r , val , 2 * x + 1, lx , m);
		set(l , r , val , 2 * x + 2 , m , rx);
		ans[x] = max(ans[2 * x + 1] , ans[2 * x + 2]);
	}

	void set(int l , int r , int val){
		set(l , r , val , 0 , 0 , siz);
	}

	int range_op(int l , int r , int x , int lx, int rx){
		if(rx <= l || r <= lx)return -1;
		if(lx >= l && rx <= r){
			return ans[x];
		}

		push(x);
		int m = (lx + rx)/2;
		return max(range_op(l , r , 2 * x + 1 , lx , m) , range_op(l , r , 2 * x + 2 , m , rx));
	}

	int range_op(int l ,int r){
		return range_op(l , r , 0 , 0 ,siz);
	}
};

void solve(){
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	Seg st;
	st.init(n + 1);
	st.build(a);

	stack<int> stk;
	vector<int> right[n + 1];
	for(int i = 0; i < n; i++){
		while(stk.size() && a[stk.top()] < a[i]){
			stk.pop();
		}
		if(stk.size()){
			//cout << stk.top() << ' ' << i << '\n';
			right[stk.top()].pb(i);
		}
		stk.push(i);
	}

	while(stk.size())stk.pop();

	for(int i = n - 1; i >= 0; i--){
		while(stk.size() && a[stk.top()] < a[i]){
			stk.pop();
		}
		if(stk.size()){
			//cout << stk.top() << ' ' << i << '\n';
			right[i].pb(stk.top());
		}
		stk.push(i);
	}

	int q;
	cin >> q;
	vector<pair<int,int>> queries[n + 1];
	int ans[q];
	for(int i = 0; i < q; i++){
		int l , r;
		cin >> l >> r;
		l--;
		r--;
		queries[l].pb(mp(r , i));
	}

	for(int i = n - 1; i >= 0; i--){
		for(int j : right[i]){
			int r = j + (j - i);
			if(r < n){
				st.set(r , n , a[i] + a[j]);
			}
		}
		for(auto j : queries[i]){
			ans[j.vs] = st.range_op(i , j.vf + 1);
		}
	}
	for(int i = 0; i < q; i++){
		cout << ans[i] << '\n';
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	//int t;
	//cin >> t;
	//while(t--)
		solve();
}

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In member function 'void Seg::build(std::vector<int>&, int, int, int)':
jumps.cpp:37:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |    if(lx < a.size()){
      |       ~~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54