oj.uz

답안 #428610

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428610 2021-06-15T13:12:56 Z abdzag 3단 점프 (JOI19_jumps) C++17
0 / 100
 4000 ms 32612 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4054 ms 32612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -