Submission #200922

#	Time	Username	Problem	Language	Result	Execution time	Memory
200922		mhy908	Triple Jump (JOI19_jumps)	C++14	100 / 100	2733 ms	54356 KiB

jumps

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=1987654321987654321;
const int inf=2000000000;
int n, q;
LL arr[500010], ans[500010];
pair<pii, int> query[500010];
vector<pii> poss;
int stck[500010], re;
struct SEGMENT_TREE{
    int x;
    struct NODE{
        LL f, arr, ans;
    }tree[2000000];
    void update_arr(int point, int s, int e, int num, LL qu){
        if(s==e){
            tree[point].arr=qu;
            tree[point].ans=tree[point].arr+tree[point].f;
            return;
        }
        int mid=(s+e)>>1;
        if(num<=mid)update_arr(point*2, s, mid, num, qu);
        else update_arr(point*2+1, mid+1, e, num, qu);
        tree[point].ans=max(max(tree[point*2].ans, tree[point*2+1].ans), tree[point*2].f+tree[point*2+1].arr);
        tree[point].f=max(tree[point*2].f, tree[point*2+1].f);
        tree[point].arr=max(tree[point*2].arr, tree[point*2+1].arr);
    }
    void update_f(int point, int s, int e, int num, LL qu){
        if(s==e){
            tree[point].f=max(tree[point].f, qu);
            tree[point].ans=tree[point].arr+tree[point].f;
            return;
        }
        int mid=(s+e)>>1;
        if(num<=mid)update_f(point*2, s, mid, num, qu);
        else update_f(point*2+1, mid+1, e, num, qu);
        tree[point].ans=max(max(tree[point*2].ans, tree[point*2+1].ans), tree[point*2].f+tree[point*2+1].arr);
        tree[point].f=max(tree[point*2].f, tree[point*2+1].f);
        tree[point].arr=max(tree[point*2].arr, tree[point*2+1].arr);
    }
    LL query_arr(int point, int s, int e, int a, int b){
        if(s>=a&&e<=b)return tree[point].arr;
        if(s>b||e<a)return -llinf;
        int mid=(s+e)>>1;
        return max(query_arr(point*2, s, mid, a, b), query_arr(point*2+1, mid+1, e, a, b));
    }
    LL query_f(int point, int s, int e, int a, int b){
        if(s>=a&&e<=b)return tree[point].f;
        if(s>b||e<a)return -llinf;
        int mid=(s+e)>>1;
        return max(query_f(point*2, s, mid, a, b), query_f(point*2+1, mid+1, e, a, b));
    }
    LL query(int point, int s, int e, int a, int b){
        if(s>=a&&e<=b)return tree[point].ans;
        if(s>b||e<a)return -llinf;
        int mid=(s+e)>>1;
        return max(max(query(point*2, s, mid, a, b), query(point*2+1, mid+1, e, a, b)), query_f(point*2, s, mid, a, b)+query_arr(point*2+1, mid+1, e, a, b));
    }
}seg;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld", &arr[i]);
        seg.update_arr(1, 1, n, i, arr[i]);
    }
    scanf("%d", &q);
    for(int i=1; i<=q; i++){
        scanf("%d %d", &query[i].F.F, &query[i].F.S);
        query[i].S=i;
    }
    for(int i=1; i<=n; i++){
        while(re&&arr[stck[re]]<=arr[i]){
            poss.pb(mp(stck[re--], i));
        }
        if(re){
            poss.pb(mp(stck[re], i));
        }
        stck[++re]=i;
    }
    sort(all(poss), greater<pii>());
    sort(query+1, query+q+1, greater<pair<pii, int> >());
    int pv=0;
    for(int i=1; i<=q; i++){
        while(pv<poss.size()&&query[i].F.F<=poss[pv].F){
            if(poss[pv].S*2-poss[pv].F<=n){
                seg.update_f(1, 1, n, poss[pv].S*2-poss[pv].F, arr[poss[pv].F]+arr[poss[pv].S]);
                //printf("inserted %d %d\n", poss[pv].F, poss[pv].S);
            }
            pv++;
        }
        //printf("answered %d %d\n", query[i].F.F, query[i].F.S);
        ans[query[i].S]=seg.query(1, 1, n, query[i].F.F, query[i].F.S);
    }
    for(int i=1; i<=q; i++)printf("%lld\n", ans[i]);
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:100:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pv<poss.size()&&query[i].F.F<=poss[pv].F){
               ~~^~~~~~~~~~~~
jumps.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
jumps.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~~~
jumps.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
jumps.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &query[i].F.F, &query[i].F.S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54