제출 #360211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
360211		mohamedsobhi777	3단 점프 (JOI19_jumps)	C++14	5 / 100	4069 ms	15724 KiB

jumps

#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;
ll A[N];
vii adj[N];
ll tree[N * 4];
ll ans[N];

void update(int idx, int val, int node = 0, int L = 1, int R = N)
{
       if (L == R)
              return void(tree[node] = max(tree[node], 1ll * 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]);
}

ll 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));
}

vi candl[N];

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[l].pb({r, i});
       }

       vii cand;
       for (int i = 0; i < n; ++i)
       {
              for (int j = i + 1; j < n; ++j)
              {
                     if (query(i + 2, j) < min(A[i], A[j]))
                     {
                            cand.pb({i, j});
                            candl[i].pb(j);
                     }
              }
       }
       for (int i = n - 1; ~i; --i)
       {
              for (auto u : candl[i])
              {
                     int a = i, b = u;
                     int c = b * 2 - a;
                     for (int j = c; j < n; ++j)
                     {
                            update(j + 1, A[a] + A[b] + A[j]);
                     }
              }
              for (auto u : adj[i])
              {
                     int l = i, r = u.f;
                     ans[u.s] = query(l + 1, r + 1);
              }
       }
       for (int i = 0; i < q; ++i)
              cout << ans[i] << "\n";
       return 0;
}

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