Submission #677662

#	Time	Username	Problem	Language	Result	Execution time	Memory
677662		jhwest2	Triple Jump (JOI19_jumps)	C++17	32 / 100	4066 ms	7036 KiB

jumps

#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 (stderr)

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 / 5
• Subtask 2: 0 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54