oj.uz

Submission #361190

# Submission time Handle Problem Language Result Execution time Memory
361190 2021-01-28T13:33:07 Z mohamedsobhi777 Triple Jump (JOI19_jumps) C++14
100 / 100
 2133 ms 129948 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 << 20);
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);
       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 89 ms 74220 KB Output is correct
2 Correct 91 ms 74288 KB Output is correct
3 Correct 82 ms 74348 KB Output is correct
4 Correct 81 ms 74220 KB Output is correct
5 Correct 81 ms 74220 KB Output is correct
6 Correct 85 ms 74244 KB Output is correct
7 Correct 82 ms 74220 KB Output is correct
8 Correct 83 ms 74220 KB Output is correct
9 Correct 89 ms 74220 KB Output is correct
10 Correct 84 ms 74220 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 74220 KB Output is correct
2 Correct 91 ms 74288 KB Output is correct
3 Correct 82 ms 74348 KB Output is correct
4 Correct 81 ms 74220 KB Output is correct
5 Correct 81 ms 74220 KB Output is correct
6 Correct 85 ms 74244 KB Output is correct
7 Correct 82 ms 74220 KB Output is correct
8 Correct 83 ms 74220 KB Output is correct
9 Correct 89 ms 74220 KB Output is correct
10 Correct 84 ms 74220 KB Output is correct
11 Correct 831 ms 90224 KB Output is correct
12 Correct 825 ms 94828 KB Output is correct
13 Correct 814 ms 94924 KB Output is correct
14 Correct 804 ms 94892 KB Output is correct
15 Correct 838 ms 94904 KB Output is correct
16 Correct 801 ms 94188 KB Output is correct
17 Correct 799 ms 94316 KB Output is correct
18 Correct 801 ms 94404 KB Output is correct
19 Correct 807 ms 94740 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 82348 KB Output is correct
2 Correct 248 ms 82028 KB Output is correct
3 Correct 247 ms 82924 KB Output is correct
4 Correct 397 ms 82344 KB Output is correct
5 Correct 432 ms 82340 KB Output is correct
6 Correct 396 ms 82284 KB Output is correct
7 Correct 397 ms 82284 KB Output is correct
8 Correct 386 ms 82284 KB Output is correct
9 Correct 408 ms 82284 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 74220 KB Output is correct
2 Correct 91 ms 74288 KB Output is correct
3 Correct 82 ms 74348 KB Output is correct
4 Correct 81 ms 74220 KB Output is correct
5 Correct 81 ms 74220 KB Output is correct
6 Correct 85 ms 74244 KB Output is correct
7 Correct 82 ms 74220 KB Output is correct
8 Correct 83 ms 74220 KB Output is correct
9 Correct 89 ms 74220 KB Output is correct
10 Correct 84 ms 74220 KB Output is correct
11 Correct 831 ms 90224 KB Output is correct
12 Correct 825 ms 94828 KB Output is correct
13 Correct 814 ms 94924 KB Output is correct
14 Correct 804 ms 94892 KB Output is correct
15 Correct 838 ms 94904 KB Output is correct
16 Correct 801 ms 94188 KB Output is correct
17 Correct 799 ms 94316 KB Output is correct
18 Correct 801 ms 94404 KB Output is correct
19 Correct 807 ms 94740 KB Output is correct
20 Correct 415 ms 82348 KB Output is correct
21 Correct 248 ms 82028 KB Output is correct
22 Correct 247 ms 82924 KB Output is correct
23 Correct 397 ms 82344 KB Output is correct
24 Correct 432 ms 82340 KB Output is correct
25 Correct 396 ms 82284 KB Output is correct
26 Correct 397 ms 82284 KB Output is correct
27 Correct 386 ms 82284 KB Output is correct
28 Correct 408 ms 82284 KB Output is correct
29 Correct 2084 ms 124140 KB Output is correct
30 Correct 1759 ms 123636 KB Output is correct
31 Correct 1668 ms 125724 KB Output is correct
32 Correct 2074 ms 124204 KB Output is correct
33 Correct 2052 ms 124232 KB Output is correct
34 Correct 2080 ms 121972 KB Output is correct
35 Correct 2054 ms 121564 KB Output is correct
36 Correct 2068 ms 121688 KB Output is correct
37 Correct 2133 ms 123036 KB Output is correct
38 Correct 1645 ms 129924 KB Output is correct
39 Correct 1638 ms 129948 KB Output is correct
40 Correct 1657 ms 126572 KB Output is correct
41 Correct 1669 ms 126060 KB Output is correct
42 Correct 1618 ms 126056 KB Output is correct
43 Correct 1700 ms 127840 KB Output is correct
44 Correct 1723 ms 129176 KB Output is correct
45 Correct 1736 ms 129392 KB Output is correct
46 Correct 1698 ms 126116 KB Output is correct
47 Correct 1715 ms 125612 KB Output is correct
48 Correct 1787 ms 125756 KB Output is correct
49 Correct 1760 ms 127864 KB Output is correct
50 Correct 1944 ms 127276 KB Output is correct
51 Correct 1930 ms 127340 KB Output is correct
52 Correct 1841 ms 124640 KB Output is correct
53 Correct 1892 ms 124416 KB Output is correct
54 Correct 1841 ms 124372 KB Output is correct
55 Correct 1827 ms 126048 KB Output is correct