oj.uz

Submission #360212

# Submission time Handle Problem Language Result Execution time Memory
360212 2021-01-27T19:46:00 Z mohamedsobhi777 Triple Jump (JOI19_jumps) C++14
5 / 100
 4000 ms 15980 KB 
#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);

       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});
       }
       stack<int> stk;
       for (int i = 0; i < n; ++i)
       {
              while (sz(stk) && A[stk.top()] < A[i])
              {
                     candl[stk.top()].pb(i);
                     stk.pop();
              }
              if (sz(stk))
              {
                     candl[stk.top()].pb(i);
              }
              stk.push(i);
       }
       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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 5 ms 5100 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5100 KB Output is correct
7 Correct 6 ms 5100 KB Output is correct
8 Correct 6 ms 5100 KB Output is correct
9 Correct 6 ms 5100 KB Output is correct
10 Correct 6 ms 5100 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 5 ms 5100 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5100 KB Output is correct
7 Correct 6 ms 5100 KB Output is correct
8 Correct 6 ms 5100 KB Output is correct
9 Correct 6 ms 5100 KB Output is correct
10 Correct 6 ms 5100 KB Output is correct
11 Execution timed out 4024 ms 15980 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 15724 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 5 ms 5120 KB Output is correct
4 Correct 5 ms 5100 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5100 KB Output is correct
7 Correct 6 ms 5100 KB Output is correct
8 Correct 6 ms 5100 KB Output is correct
9 Correct 6 ms 5100 KB Output is correct
10 Correct 6 ms 5100 KB Output is correct
11 Execution timed out 4024 ms 15980 KB Time limit exceeded
12 Halted 0 ms 0 KB -