Submission #158536

#	Time	Username	Problem	Language	Result	Execution time	Memory
158536		bicsi	Triple Jump (JOI19_jumps)	C++14	0 / 100	420 ms	52216 KiB

jumps

#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() > 15) 
        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], i));    
        pqs[i] = now;
    }
 
    now = PQ();
    for (int i = m; i >= b; --i) {
        Add(now, make_pair(-v[i], 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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54