oj.uz

답안 #398491

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
398491 2021-05-04T11:47:16 Z nikatamliani 3단 점프 (JOI19_jumps) C++14
32 / 100
 324 ms 39448 KB 
#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];
	}
}

Compilation message

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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9704 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9652 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 8 ms 9700 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9704 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9652 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 8 ms 9700 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Runtime error 324 ms 39448 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 31844 KB Output is correct
2 Correct 198 ms 31476 KB Output is correct
3 Correct 197 ms 32400 KB Output is correct
4 Correct 288 ms 31768 KB Output is correct
5 Correct 282 ms 31800 KB Output is correct
6 Correct 268 ms 31192 KB Output is correct
7 Correct 261 ms 30916 KB Output is correct
8 Correct 266 ms 31004 KB Output is correct
9 Correct 276 ms 31380 KB Output is correct

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9704 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9652 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 8 ms 9700 KB Output is correct
10 Correct 6 ms 9676 KB Output is correct
11 Runtime error 324 ms 39448 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -