oj.uz

Submission #158538

# Submission time Handle Problem Language Result Execution time Memory
158538 2019-10-17T16:34:11 Z bicsi Triple Jump (JOI19_jumps) C++14
0 / 100
 393 ms 36472 KB 
#include <bits/stdc++.h>

using namespace std;

template <class T>
struct RMQ {
  vector<vector<T>> rmq;
  
  void Build(const vector<T>& V) {
    int n = V.size(), on = 1, depth = 1;
    while (on < n) on *= 2, ++depth;
    rmq.assign(depth, V);
    
    for (int i = 0; i < depth - 1; ++i)
      for (int j = 0; j < n; ++j) {
        rmq[i + 1][j] = max(rmq[i][j],
            rmq[i][min(n - 1, j + (1 << i))]);
      }
  }
  
  T Query(int a, int b) {
    if (b <= a) return 0;
    int dep = 31 - __builtin_clz(b - a); // log(b - a)
    return max(rmq[dep][a], rmq[dep][b - (1 << dep)]);
  }
};

using PQ = priority_queue<pair<int, int>>;
RMQ<int> rmq;
vector<vector<pair<int, int>>> queries;
vector<int> answer;
vector<PQ> pqs;
vector<int> v;

void Add(PQ& a, pair<int, int> x) {
    a.push(x);
    while (a.size() > 5) 
        a.pop();
}
void Merge(PQ& a, PQ b) {
    while (!b.empty()) {
        auto top = b.top();
        Add(a, top);
        b.pop();
    }
}

int Solve(int l, int r, PQ& pq) {
    vector<int> vals;
    vals.reserve(pq.size());
    while (pq.size()) {
        vals.push_back(pq.top().second);
        pq.pop();
    }
    
    int best = 0;
    for (auto a : vals) {
        for (auto b : vals) {
            if (a >= b) continue;
            
            int delta = b - a;
            int now = 0;
            now = max(now, rmq.Query(a + 1, a + delta / 2 + 1));
            now = max(now, rmq.Query(max(l, a - delta), a));
            now = max(now, rmq.Query(b + delta, r + 1));
            best = max(best, now + v[a] + v[b]);
        }
    }
    return best;
}

void Divide(int b, int e) {
    if (b == e) {
        return; 
    }

    int m = (b + e) / 2;
    Divide(b, m); Divide(m + 1, e);
    PQ now;
    for (int i = m + 1; i <= e; ++i) {
        Add(now, make_pair(v[i] * (-10) + rand() % 10, i));    
        pqs[i] = now;
    }

    now = PQ();
    for (int i = m; i >= b; --i) {
        Add(now, make_pair(v[i] * (-10) + rand() % 10, i));
        while (queries[i].size()) {
            int j, idx; tie(j, idx) = queries[i].back();
            if (j > e) break;
            queries[i].pop_back();
            PQ now2 = now;
            Merge(now2, pqs[j]);
            answer[idx] = Solve(i, j, now2);
        }    
    }
}

int main() {
    int n; cin >> n;
    
    v.resize(n);
    for (int i = 0; i < n; ++i) 
        cin >> v[i];
    
    rmq.Build(v);
    
    int q; cin >> q;    
    queries.assign(n, {});
    answer.assign(q, -1);
    pqs.assign(n, PQ());

    for (int i = 0; i < q; ++i) {
        int l, r; cin >> l >> r; --l; --r;
        queries[l].emplace_back(r, i);    
    }

    Divide(0, n - 1);
    for (int i = 0; i < q; ++i)
        cout << answer[i] << '\n';


    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 36420 KB Output is correct
2 Correct 373 ms 36340 KB Output is correct
3 Correct 367 ms 36472 KB Output is correct
4 Incorrect 381 ms 36360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -