oj.uz

Submission #361189

# Submission time Handle Problem Language Result Execution time Memory
361189 2021-01-28T13:31:25 Z mohamedsobhi777 Triple Jump (JOI19_jumps) C++14
32 / 100
 460 ms 61096 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 = (1 << 18);
const ll mod = 1e9 + 7;
const ll inf = 2e18;

int n, q;
ll A[N];
vii adj[N];
ll ans[N];

struct node
{
       int a, b, ab;
       node() { a = b = ab = 0; }
       node(int a, int b, int ab) : a(a), b(b), ab(ab) {}
       node operator+=(node ohs)
       {
              ab = max(max(ab, ohs.ab), a + ohs.b);
              a = max(a, ohs.a);
              b = max(b, ohs.b);
              return *this;
       }
} tree[N * 2];

node get(node lhs, node rhs)
{
       node ret;
       ret.a = max(lhs.a, rhs.a);
}

void pull(int v)
{
       tree[v] = tree[v * 2];
       tree[v] += tree[v * 2 + 1];
}

void build(int v = 1, int L = 0, int R = N - 1)
{
       if (L == R)
       {
              tree[v] = node(0, A[L], 0);
              return;
       }
       int mid = (L + R) >> 1;
       build(v * 2, L, mid), build(v * 2 + 1, mid + 1, R);
       pull(v);
}

void update(int st, int va, int v = 1, int L = 0, int R = N - 1)
{
       if (st < L || st > R)
              return;
       if (L == R)
       {
              tree[v].a = max(tree[v].a, va);
              tree[v].ab = max(tree[v].ab, tree[v].a + tree[v].b);
              return;
       }
       int mid = (L + R) >> 1;
       update(st, va, v * 2, L, mid);
       update(st, va, v * 2 + 1, mid + 1, R);
       pull(v);
}

node get(int st, int en, int v = 1, int L = 0, int R = N - 1)
{
       if (st > R || en < L)
              return node();
       if (L >= st && R <= en)
              return tree[v];
       int mid = (L + R) >> 1;
       node ret = get(st, en, v * 2, L, mid);
       ret += get(st, en, v * 2 + 1, mid + 1, R);
       return ret;
}

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];
       build();
       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;
                     if (c < n)
                            update(c, A[a] + A[b]);
              }
              for (auto u : adj[i])
              {
                     node ret = get(i, u.f);
                     ans[u.s] = ret.ab;
              }
       }
       for (int i = 0; i < q; ++i)
              cout << ans[i] << "\n";
       return 0;
}

Compilation message

jumps.cpp: In function 'node get(node, node)':
jumps.cpp:67:1: warning: no return statement in function returning non-void [-Wreturn-type]
   67 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18936 KB Output is correct
2 Correct 21 ms 18796 KB Output is correct
3 Correct 24 ms 18796 KB Output is correct
4 Correct 22 ms 18796 KB Output is correct
5 Correct 21 ms 18796 KB Output is correct
6 Correct 22 ms 19072 KB Output is correct
7 Correct 22 ms 18796 KB Output is correct
8 Correct 22 ms 18796 KB Output is correct
9 Correct 22 ms 18796 KB Output is correct
10 Correct 21 ms 18796 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18936 KB Output is correct
2 Correct 21 ms 18796 KB Output is correct
3 Correct 24 ms 18796 KB Output is correct
4 Correct 22 ms 18796 KB Output is correct
5 Correct 21 ms 18796 KB Output is correct
6 Correct 22 ms 19072 KB Output is correct
7 Correct 22 ms 18796 KB Output is correct
8 Correct 22 ms 18796 KB Output is correct
9 Correct 22 ms 18796 KB Output is correct
10 Correct 21 ms 18796 KB Output is correct
11 Runtime error 460 ms 61096 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 28652 KB Output is correct
2 Correct 194 ms 28432 KB Output is correct
3 Correct 181 ms 29164 KB Output is correct
4 Correct 318 ms 28668 KB Output is correct
5 Correct 324 ms 28652 KB Output is correct
6 Correct 310 ms 28012 KB Output is correct
7 Correct 313 ms 27884 KB Output is correct
8 Correct 336 ms 28012 KB Output is correct
9 Correct 318 ms 28140 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18936 KB Output is correct
2 Correct 21 ms 18796 KB Output is correct
3 Correct 24 ms 18796 KB Output is correct
4 Correct 22 ms 18796 KB Output is correct
5 Correct 21 ms 18796 KB Output is correct
6 Correct 22 ms 19072 KB Output is correct
7 Correct 22 ms 18796 KB Output is correct
8 Correct 22 ms 18796 KB Output is correct
9 Correct 22 ms 18796 KB Output is correct
10 Correct 21 ms 18796 KB Output is correct
11 Runtime error 460 ms 61096 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -