제출 #398491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398491		nikatamliani	3단 점프 (JOI19_jumps)	C++14	32 / 100	324 ms	39448 KiB

jumps

#include "bits/stdc++.h"
#define ll long long
using namespace std;
template <typename T, typename Lambda>
struct segment_tree {
    vector<T> tree;
    T neutral;
    Lambda join;
    int size, real_size;
    segment_tree() {}
    template <typename L>
    segment_tree(int _size, const T &_neutral, const L& f)
        : join (f) {
        real_size = _size;
        size = nxt(_size);
        tree = vector<T>(2*size+1);
        neutral = _neutral;
    }
    
    int nxt(int x) {
        int i = 1;
        while(i < x) {
            i <<= 1;
        }
        return i;
    }
    
    void init(const vector<T> &v) {
        for(int i = 0; i < real_size; ++i) {
            tree[i + size] = v[i];
        }
        for(int i = size - 1; i >= 0; --i) {
            tree[i] = join(tree[i << 1], tree[i << 1 | 1]);
        }
    }
    
    void point_update(int id, const T &val) {
//      point_update(1, size, id, val, 1); 
        point_update_iterative(id, val);
    }
    
    void point_update_iterative(int id, const T &val) {
        id += size - 1;
        tree[id] = val;
        id >>= 1;
        while(id > 0) {
            tree[id] = join(tree[id << 1], tree[id << 1 | 1]);
            id >>= 1;
        }
    }
    
    
    void point_update(int l, int r, int x, const T &val, int p) {
        if(l > x || r < x) {
            return;
        }
        if(l == r) {
            tree[p] = val;
            return;
        }
        int middle = l + r >> 1;
        point_update(l, middle, x, val, p << 1);
        point_update(middle+1, r, x, val, p << 1 | 1);
        tree[p] = join(tree[p << 1], tree[p << 1 | 1]);
    }
    
    T get(int id) {
        return query(id, id);
    }
    
    T query(int L, int R) {
		return query(1, size, L, R, 1);
    }
    
    T query_iterative(int L, int R) {
        L += size - 1;
        R += size - 1;
        T ans = neutral;
        while(L <= R) {
            if(L & 1) {
                ans = join(ans, tree[L++]);
            }
            if(!(R & 1)) {
                ans = join(ans, tree[R--]);
            }
            L >>= 1;
            R >>= 1;
        }
        return ans;
    }
    
    T query(int l, int r, int L, int R, int p) {
        if(L > r || l > R) return neutral;
        if(L <= l && R >= r) return tree[p];
        int middle = l + r >> 1;
        T lft = query(l, middle, L, R, p << 1);
        T rgh = query(middle+1, r, L, R, p << 1 | 1);
        return join(lft, rgh);
    }
};
const int N = 2e5+10;
ll n, q, a[N], ans[N];
vector<int> candidates[N];
vector<pair<int, int>> queries[N];
struct node {
	ll a, b, c;
	node() {
		a = b = c = 0;
	}
	node(ll _a, ll _b, ll _c) : a(_a), b(_b), c(_c) {}
};
int main() {
	auto join = [](const node &x, const node &y) {
		node ans;
		ans.a = max(x.a, y.a);
		ans.b = max(x.b, y.b);
		ans.c = max({x.c, y.c, x.a + y.b});
		return ans;
	};
	cin >> n;
	segment_tree<node, decltype(join)> t(n, node(), join);
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		node x(0, a[i], a[i]);
		t.point_update(i, x);
	}
	stack<int> st;
	for(int i = 1; i <= n; ++i) {
		while(!st.empty() && a[st.top()] <= a[i]) {
			candidates[st.top()].push_back(i);
			st.pop();
		}
		if(!st.empty()) {
			candidates[st.top()].push_back(i);
		}
		st.push(i);
	}
	cin >> q;
	for(int i = 1; i <= q; ++i) {
		int l, r; cin >> l >> r;
		queries[l].push_back({r, i});
	}
	for(int l = n; l >= 1; --l) {
		for(int i : candidates[l]) {
			int id = 2*i - l;
			if(id <= n) {
				node x = t.get(id);
				x.a = max(x.a, a[i] + a[l]);
				x.c = x.a + x.b;
				t.point_update(id, x);
			}
		}
		for(pair<int, int> p : queries[l]) {
			ans[p.second] = t.query(l, p.first).c;
		}
	}
	for(int i = 1; i <= q; ++i) {
		cout << ans[i] << " \n"[i == n];
	}
}

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

jumps.cpp: In instantiation of 'T segment_tree<T, Lambda>::query(int, int, int, int, int) [with T = node; Lambda = main()::<lambda(const node&, const node&)>]':
jumps.cpp:72:32:   required from 'T segment_tree<T, Lambda>::query(int, int) [with T = node; Lambda = main()::<lambda(const node&, const node&)>]'
jumps.cpp:154:38:   required from here
jumps.cpp:95:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |         int middle = l + r >> 1;
      |                      ~~^~~

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