oj.uz

Submission #495610

# Submission time Handle Problem Language Result Execution time Memory
495610 2021-12-19T13:08:07 Z 600Mihnea Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 34388 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 5e5 + 7;
const int K = 19;
const int INF = (int) 1e9 + 7;
int n;
int q;
int a[N];
int lg[N];
int maxA[K][N];
int nextBigger[N];

int getMaxA(int l, int r) {
  if (l > r) {
    return -INF;
  }
  assert(1 <= l && l <= r && r <= n);
  int k = lg[r - l + 1];
  return max(maxA[k][l], maxA[k][r - (1 << k) + 1]);
}

struct Offer {
  int value;
  int lft;
  int rgh;
};

struct Question {
  int l;
  int r;
  int ind;
};

bool operator < (Offer a, Offer b) {
  return a.lft > b.lft;
}

vector<Question> questionsAt[N];
int best[N];


signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  //freopen ("input", "r", stdin);


  cin >> n;
  for (int i = 2; i <= n; i++) {
    lg[i] = lg[i / 2] + 1;
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    maxA[0][i] = a[i];
  }
  for (int k = 1; (1 << k) <= n; k++) {
    for (int i = 1; i + (1 << k) - 1 <= n; i++) {
      maxA[k][i] = max(maxA[k - 1][i], maxA[k - 1][i + (1 << (k - 1))]);
    }
  }

  { /// just some stack bro
    vector<int> stk;
    for (int i = n; i >= 1; i--) {
      while (!stk.empty() && a[i] >= a[stk.back()]) {
        stk.pop_back();
      }
      nextBigger[i] = (stk.empty() ? (n + 1) : stk.back());
      stk.push_back(i);
    }
  }

  vector<Offer> offers;

  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= min(n, nextBigger[i]); j = nextBigger[j]) {
      if (2 * j - i <= n) {
        offers.push_back({a[i] + a[j], i, 2 * j - i});
      }
    }
  }

  sort(offers.begin(), offers.end());


  cin >> q;
  vector<int> solPrint(q, -1);
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    questionsAt[l].push_back({l, r, i});
  }

  for (int i = 1; i <= n; i++) {
    best[i] = -INF;
  }

  int last = -1;

  for (int l = n; l >= 1; l--) {
    while (last + 1 < (int) offers.size() && l <= offers[last + 1].lft) {
      last++;
      for (int r = offers[last].rgh; r <= n; r++) {
        best[r] = max(best[r], offers[last].value + a[r]);
      }
    }
    for (auto &it : questionsAt[l]) {
      int r = it.r, ind = it.ind, maximum = 0;
      for (int j = l; j <= r; j++) {
        maximum = max(maximum, best[j]);
      }
      solPrint[ind] = maximum;
    }
  }

  for (auto &x : solPrint) {
    assert(x != -1);
    cout << x << "\n";
  }



  return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 6 ms 12108 KB Output is correct
3 Correct 6 ms 12108 KB Output is correct
4 Correct 7 ms 12108 KB Output is correct
5 Correct 6 ms 12108 KB Output is correct
6 Correct 7 ms 12108 KB Output is correct
7 Correct 6 ms 12108 KB Output is correct
8 Correct 6 ms 12108 KB Output is correct
9 Correct 6 ms 12108 KB Output is correct
10 Correct 6 ms 12108 KB Output is correct
11 Correct 995 ms 29740 KB Output is correct
12 Correct 967 ms 34180 KB Output is correct
13 Correct 1012 ms 34188 KB Output is correct
14 Correct 973 ms 34344 KB Output is correct
15 Correct 966 ms 34388 KB Output is correct
16 Correct 963 ms 33752 KB Output is correct
17 Correct 971 ms 33696 KB Output is correct
18 Correct 976 ms 33568 KB Output is correct
19 Correct 962 ms 34240 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4081 ms 33800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 6 ms 12108 KB Output is correct
3 Correct 6 ms 12108 KB Output is correct
4 Correct 7 ms 12108 KB Output is correct
5 Correct 6 ms 12108 KB Output is correct
6 Correct 7 ms 12108 KB Output is correct
7 Correct 6 ms 12108 KB Output is correct
8 Correct 6 ms 12108 KB Output is correct
9 Correct 6 ms 12108 KB Output is correct
10 Correct 6 ms 12108 KB Output is correct
11 Correct 995 ms 29740 KB Output is correct
12 Correct 967 ms 34180 KB Output is correct
13 Correct 1012 ms 34188 KB Output is correct
14 Correct 973 ms 34344 KB Output is correct
15 Correct 966 ms 34388 KB Output is correct
16 Correct 963 ms 33752 KB Output is correct
17 Correct 971 ms 33696 KB Output is correct
18 Correct 976 ms 33568 KB Output is correct
19 Correct 962 ms 34240 KB Output is correct
20 Execution timed out 4081 ms 33800 KB Time limit exceeded
21 Halted 0 ms 0 KB -