#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
pii bigger(pii x, pii y){
if(x.fi != y.fi){
return (x.fi > y.fi ? x : y);
}
return x;
}
const int MAXN = 5e5 + 7;
const int MAXK = 22;
const int BASE = (1 << 19);
int a[MAXN];
pii tree[2 * BASE + 7];
int lg[4 * MAXN];
int m[MAXK][MAXN];
ll best[MAXN];
vector<pii> queries[MAXN];
ll ans[MAXN];
int n, q;
void init(){
for(int i = 1; i <= n; i++){
tree[i + BASE] = {a[i], i};
}
for(int i = BASE - 1; i >= 1; i--){
tree[i] = bigger(tree[2 * i], tree[2 * i + 1]);
}
lg[1] = 0;
for(int i = 2; i < MAXN; i++){
lg[i] = lg[i / 2] + 1;
}
for(int i = 1; i <= n; i++){
m[0][i] = a[i];
}
for(int j = 1; j < MAXK; j++){
for(int i = 1; i <= n; i++){
m[j][i] = max(m[j - 1][i], m[j - 1][min(n, i + (1 << (j - 1)))]);
}
}
}
int getMx(int l, int p){
if(p < l){
return 0;
}
return max(m[lg[p - l + 1]][l], m[lg[p - l + 1]][p - (1 << lg[p - l + 1]) + 1]);
}
void upd(int ind, pii val){
ind += BASE;
tree[ind] = val;
ind /= 2;
while(ind > 0){
tree[ind] = bigger(tree[2 * ind], tree[2 * ind + 1]);
ind /= 2;
}
}
int x, y;
pii query(int v, int l, int p){
if(p < x || y < l){
return {0, 0};
}
if(x <= l && p <= y){
return tree[v];
}
int mid = (l + p) / 2;
return bigger(query(2 * v, l, mid), query(2 * v + 1, mid + 1, p));
}
ll solve(int l, int p){
x = l;
y = p;
int k = min(22, p - l + 1);
vi vec;
for(int i = 0; i < k; i++){
pii akt = query(1, 0, BASE - 1);
vec.pb(akt.se);
upd(akt.se, {0, akt.se});
}
sort(all(vec));
for(int i = 0; i < k; i++){
upd(vec[i], {a[vec[i]], vec[i]});
}
ll res = 0;
for(int i = 0; i < k; i++){
for(int j = i + 1; j < k; j++){
if(vec[i] == vec[j]){
continue;
}
ll akt = (ll)a[vec[i]] + a[vec[j]];
if(max(l, vec[i] - (vec[j] - vec[i])) <= vec[i] - 1){
res = max(res, (ll)akt + getMx(max(l, vec[i] - (vec[j] - vec[i])), vec[i] - 1));
}
if(vec[i] + 1 != vec[j]){
res = max(res, (ll)akt + getMx(vec[i] + 1, vec[i] + (vec[j] - vec[i]) / 2));
}
if(2 * vec[j] - vec[i] <= p){
res = max(res, (ll)akt + getMx(2 * vec[j] - vec[i], p));
}
//cout << vec[i] << ' ' << vec[j] << ' ' << res << '\n';
}
}
return res;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
lg[1] = 0;
for(int i = 2; i < MAXN; i++){
lg[i] = lg[i / 2] + 1;
}
for(int i = 1; i <= n; i++){
m[0][i] = a[i];
}
for(int j = 1; j < MAXK; j++){
for(int i = 1; i <= n; i++){
m[j][i] = max(m[j - 1][i], m[j - 1][min(n, i + (1 << (j - 1)))]);
}
}
cin >> q;
for(int i = 1; i <= q; i++){
int l, p;
cin >> l >> p;
queries[p].pb({l, i});
}
for(int i = 3; i <= n; i++){
sort(all(queries[i]));
pii akt = (sz(queries[i]) == 0 ? mp(0, 0) : queries[i].back());
for(int j = i - 2; j >= 1; j--){
best[j] = max(best[j], max(best[j + 1], (ll)a[j] + a[i] + getMx(j + 1, j + (i - j) / 2)));
// cout << i << ' ' << j << ' ' << best[j] << '\n';
if(akt.fi == j){
ans[akt.se] = best[j];
if(sz(queries[i])){
queries[i].pop_back();
akt = (sz(queries[i]) == 0 ? mp(0, 0) : queries[i].back());
}
}
}
}
for(int i = 1; i <= q; i++){
cout << ans[i] << '\n';
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
14168 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14172 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
14172 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
14168 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14172 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
14172 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4034 ms |
34384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
14168 KB |
Output is correct |
| 2 |
Correct |
7 ms |
14172 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
14172 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
