| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 428610 |
2021-06-15T13:12:56 Z |
abdzag |
Triple Jump (JOI19_jumps) |
C++17 |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4054 ms |
32612 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
