#include <bits/stdc++.h>
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
using namespace std;
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)
using lll = __int128;
using ll = long long;
using ld = long double;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
int n, q;
int A[N];
vii adj[N];
int tree[N * 4];
int ans[N];
void update(int idx, int val, int node = 0, int L = 1, int R = N)
{
if (L == R)
return void(tree[node] = val);
int mid = (L + R) >> 1;
update(idx, val, node * 2 + 1 + (idx > mid), (idx > mid ? mid + 1 : L), (idx > mid ? R : mid));
tree[node] = max(tree[node * 2 + 1], tree[node * 2 + 2]);
}
int query(int l, int r, int node = 0, int L = 1, int R = N)
{
if (l > r || l > R || r < L)
return 0;
if (L >= l && R <= r)
return tree[node];
int mid = (L + R) >> 1;
return max(query(l, r, node * 2 + 1, L, mid), query(l, r, node * 2 + 2, mid + 1, R));
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> A[i];
update(i + 1, A[i]);
}
cin >> q;
for (int i = 0; i < q; ++i)
{
int l, r;
cin >> l >> r;
--l, --r;
adj[r].pb({l, i});
}
vii cand;
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
if (query(i + 1, j - 1) < min(A[i], A[j]))
{
cand.pb({i, j});
}
}
}
for (int i = 0; i < n; ++i)
{
for (auto u : adj[i])
{
int ret = 0;
int l = u.f, r = i;
for (auto u0 : cand)
{
int a = u0.f, b = u0.s, c = u0.s * 2 - u0.f;
if (a >= l && b <= r && c <= r)
{
ret = max(ret, A[a] + A[b] + query(c + 1, r + 1));
}
}
ans[u.s] = ret;
}
}
for (int i = 0; i < q; ++i)
cout << ans[i] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2668 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2668 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
8172 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2668 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
