제출 #428610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428610		abdzag	3단 점프 (JOI19_jumps)	C++17	0 / 100	4054 ms	32612 KiB

jumps

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const long long inf = 2e9;

using namespace std;
struct Tree {
	typedef pair<int, int> T;
	static constexpr T unit = make_pair(INT_MIN, INT_MIN);
	T f(T a, T b) { return max(a, b); } // (any associative fn)
	vector<T> s; int n;
	Tree(int n = 0, T def = unit) : s(2 * n, def), n(n) {}
	void update(int pos, T val) {
		for (s[pos += n] = val; pos /= 2;)
			s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
	}
	T query(int b, int e) { // query [b, e)
		T ra = unit, rb = unit;
		for (b += n, e += n; b < e; b /= 2, e /= 2) {
			if (b % 2) ra = f(ra, s[b++]);
			if (e % 2) rb = f(s[--e], rb);
		}
		return f(ra, rb);
	}
};

int main() {
	cin.sync_with_stdio(false);
	ll n;
	cin >> n;
	vector<int> v(n);
	rep(i, 0, n)cin >> v[i];
	Tree tree(n);
	rep(i, 0, n)tree.update(i, make_pair(v[i], i));
	ll q;
	vector<set<ll>> vec(n);
	vector<bool> visited(n);
	rep(i, 0, n-2) {
		ll cur = i + 1;
		ll a = i;
		ll b = i + 1;
		ll last = -1;
		while (cur != n) {
			if (v[b] < v[cur])b = cur;
			if (tree.query(a, b).first > v[a]) {
				last = a;
				a = tree.query(a, b).second;
			}
			if (visited[a])break;
			if(last!=-1)visited[last] = 1;
			vec[a].insert(b);
			cur++;
		}
	}
	cin >> q;
	vector<pair<pair<ll, ll>,ll>> qs(q);
	rep(i, 0, q) {
		cin >> qs[i].first.first >> qs[i].first.second;
		qs[i].first.first--;
		qs[i].second = i;
	}
	sort(all(qs), greater<>());
	Tree vecc(n);
	rep(i, 0, n)vecc.update(i, make_pair(v[i],i));
	cout << endl;
	vector<ll> ans(q);
	ll cur = n-1;
	rep(i, 0, q) {
		rrep(j, cur, qs[i].first.first-1) {
			trav(a, vec[j]) {
				rep(o, 2 * a - j, n) {
					if (vecc.query(o, o + 1).first < v[a] + v[j] + v[o]) {
						vecc.update(o, make_pair(v[a] + v[j] + v[o],i));
					}
				}
			}
		}
		ans[qs[i].second] = vecc.query(qs[i].first.first, qs[i].first.second).first;
		cur = qs[i].first.first - 1;
	}
	trav(a, ans)cout << a << endl;
	return 0;
}

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