oj.uz

Submission #679063

# Submission time Handle Problem Language Result Execution time Memory
679063 2023-01-07T11:04:27 Z Cross_Ratio Triple Jump (JOI19_jumps) C++14
27 / 100
 213 ms 33192 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct SegTree {
    struct Node {
        int v;
        int lz, ma;
        Node(int _v, int _l, int _m) : v(_v), lz(_l), ma(_m){}
        Node() : v(0), lz(0), ma(0) {}
    };
    vector<Node> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i].ma = max(seg[2*i].ma, seg[2*i+1].ma);
        }
    }
    void prop(int n, int ns, int ne) {
        if(seg[n].lz!=0) {
            seg[n].v = max(seg[n].v, seg[n].lz + seg[n].ma);
            if(n<MAX/2) {
                seg[2*n].lz = max(seg[2*n].lz, seg[n].lz);
                seg[2*n+1].lz = max(seg[2*n+1].lz, seg[n].lz);
            }
            seg[n].lz = 0;
        }
    }
    void add(int s, int e, int k, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            seg[n].lz = max(seg[n].lz, k);
            prop(n,ns,ne);
            return;
        }
        int mid = ns + ne >> 1;
        add(s, e, k, 2*n, ns, mid);
        add(s, e, k, 2*n+1, mid, ne);
        if(n<MAX/2) seg[n].v = max(seg[2*n].v, seg[2*n+1].v);
    }
    int sum(int s, int e, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n].v;
        int mid = ns + ne >> 1;
        return max(sum(s, e, 2*n, ns, mid), sum(s, e, 2*n+1, mid, ne));
    }
};
int A[500005];
int L[500005];
int R[500005];
int ans[500005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    for(i=0;i<N;i++) cin >> A[i];
    vector<int> V;
    vector<vector<int>> Q1, Q2;
    Q1.resize(N), Q2.resize(N);
    for(i=0;i<N;i++) {
        while(V.size()&&A[V.back()]<=A[i]) {
            Q1[V.back()].push_back(i);
            V.pop_back();
        }
        if(V.size()) Q1[V.back()].push_back(i);
        V.push_back(i);
    }
    int Q;
    cin >> Q;
    for(i=0;i<Q;i++) {
        cin >> L[i] >> R[i];
        L[i]--, R[i]--;
        Q2[L[i]].push_back(i);
    }
    SegTree tree(N+5);
    int MAX = tree.MAX;
    for(i=0;i<N;i++) {
        tree.seg[i+MAX/2].ma = A[i];
    }
    tree.cons();
    for(i=N-1;i>=0;i--) {
        for(int k : Q1[i]) {
            if(2*k-i<N) {
                tree.add(2*k-i, N, A[i] + A[k], 1, 0, MAX/2);
            }
        }
        for(int v : Q2[i]) {
            ans[v] = tree.sum(L[i]+2, R[i]+1, 1, 0, MAX/2);
        }
    }
    for(i=0;i<Q;i++) cout << ans[i] << '\n';
}

Compilation message

jumps.cpp: In member function 'void SegTree::add(long long int, long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:42:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
jumps.cpp: In member function 'long long int SegTree::sum(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:51:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:65:12: warning: unused variable 'j' [-Wunused-variable]
   65 |     int i, j;
      |            ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 32848 KB Output is correct
2 Correct 118 ms 31604 KB Output is correct
3 Correct 117 ms 33192 KB Output is correct
4 Correct 212 ms 32840 KB Output is correct
5 Correct 207 ms 32844 KB Output is correct
6 Correct 204 ms 32072 KB Output is correct
7 Correct 208 ms 32092 KB Output is correct
8 Correct 202 ms 32092 KB Output is correct
9 Correct 203 ms 32416 KB Output is correct

Subtask #4
0 / 54.0

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