oj.uz

Submission #677662

# Submission time Handle Problem Language Result Execution time Memory
677662 2023-01-04T06:35:54 Z jhwest2 Triple Jump (JOI19_jumps) C++17
32 / 100
 4000 ms 7036 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 505050;
const int B = 20;
int n, q, a[N];

struct SEG {
    int tree[N * 4];

    void init(int l, int r, int x) {
        if (l == r) {
            tree[x] = a[l];
            return;
        }
        int m = (l + r) / 2;
        init(l, m, 2 * x);
        init(m + 1, r, 2 * x + 1);
        tree[x] = max(tree[2 * x], tree[2 * x + 1]);
    }
    int query(int a, int b, int l, int r, int x) {
        if (b < l || a > r) 
            return 0;
        if (a <= l && r <= b)
            return tree[x];
        int m = (l + r) / 2;
        return max(query(a, b, l, m, 2 * x), query(a, b, m + 1, r, 2 * x + 1));
    }   
} t1;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> a[i];
    t1.init(1, n, 1);

    cin >> q;
    while (q--) { // O(n log n + log^3 n) per each query
        int l, r; cin >> l >> r;

        vector<pair<int, int>> v;
        for (int i = l; i <= r; i++)    
            v.push_back({a[i], i});
        sort(v.rbegin(), v.rend());

        // largest log_2 n elements are critical
        vector<int> p;
        for (int i = 0; i < min(B, (int)v.size()); i++) 
            p.push_back(v[i].second);
        sort(p.begin(), p.end());

        int ans = 0;
        // use three
        for (int i = 0; i < p.size(); i++) for (int j = i + 1; j < p.size(); j++) for (int k = j + 1; k < p.size(); k++) {
            if (p[j] - p[i] <= p[k] - p[j])
                ans = max(ans, a[p[i]] + a[p[j]] + a[p[k]]);
        }
        // use one or two
        for (int i = 0; i < p.size(); i++) for (int j = l; j <= r; j++) {
            int x = p[i], y = j;

            if (x == y) 
                continue;
            if (x > y)
                swap(x, y);

            int d = y - x;
            // left
            ans = max(ans, a[x] + a[y] + t1.query(max(x - d, l), x - 1, 1, n, 1));
            
            // middle
            if (x < x + d / 2)
                ans = max(ans, a[x] + a[y] + t1.query(x + 1, x + d / 2, 1, n, 1));
            
            // right
            if (y + d <= r)
                ans = max(ans, a[x] + a[y] + t1.query(y + d, r, 1, n, 1));
        }
        cout << ans << '\n';
    }
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 0; i < p.size(); i++) for (int j = i + 1; j < p.size(); j++) for (int k = j + 1; k < p.size(); k++) {
      |                         ~~^~~~~~~~~~
jumps.cpp:55:66: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 0; i < p.size(); i++) for (int j = i + 1; j < p.size(); j++) for (int k = j + 1; k < p.size(); k++) {
      |                                                                ~~^~~~~~~~~~
jumps.cpp:55:105: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int i = 0; i < p.size(); i++) for (int j = i + 1; j < p.size(); j++) for (int k = j + 1; k < p.size(); k++) {
      |                                                                                                       ~~^~~~~~~~~~
jumps.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int i = 0; i < p.size(); i++) for (int j = l; j <= r; j++) {
      |                         ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 12 ms 340 KB Output is correct
3 Correct 10 ms 340 KB Output is correct
4 Correct 9 ms 336 KB Output is correct
5 Correct 9 ms 332 KB Output is correct
6 Correct 10 ms 324 KB Output is correct
7 Correct 13 ms 336 KB Output is correct
8 Correct 10 ms 340 KB Output is correct
9 Correct 12 ms 340 KB Output is correct
10 Correct 12 ms 340 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 12 ms 340 KB Output is correct
3 Correct 10 ms 340 KB Output is correct
4 Correct 9 ms 336 KB Output is correct
5 Correct 9 ms 332 KB Output is correct
6 Correct 10 ms 324 KB Output is correct
7 Correct 13 ms 336 KB Output is correct
8 Correct 10 ms 340 KB Output is correct
9 Correct 12 ms 340 KB Output is correct
10 Correct 12 ms 340 KB Output is correct
11 Execution timed out 4066 ms 748 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1356 ms 6984 KB Output is correct
2 Correct 1261 ms 6984 KB Output is correct
3 Correct 1020 ms 6984 KB Output is correct
4 Correct 1251 ms 7036 KB Output is correct
5 Correct 1300 ms 6988 KB Output is correct
6 Correct 1306 ms 6344 KB Output is correct
7 Correct 1370 ms 6256 KB Output is correct
8 Correct 1420 ms 6336 KB Output is correct
9 Correct 1393 ms 6636 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 12 ms 340 KB Output is correct
3 Correct 10 ms 340 KB Output is correct
4 Correct 9 ms 336 KB Output is correct
5 Correct 9 ms 332 KB Output is correct
6 Correct 10 ms 324 KB Output is correct
7 Correct 13 ms 336 KB Output is correct
8 Correct 10 ms 340 KB Output is correct
9 Correct 12 ms 340 KB Output is correct
10 Correct 12 ms 340 KB Output is correct
11 Execution timed out 4066 ms 748 KB Time limit exceeded
12 Halted 0 ms 0 KB -