Submission #200925

#	Time	Username	Problem	Language	Result	Execution time	Memory
200925		mhy908	Triple Jump (JOI19_jumps)	C++14	100 / 100	1178 ms	52688 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;
        NODE operator+(NODE a){
            return {max(f, a.f), max(arr, a.arr), max(max(ans, a.ans), f+a.arr)};
        }
    }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]=tree[point*2]+tree[point*2+1];
    }
    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]=tree[point*2]+tree[point*2+1];
    }
    NODE query(int point, int s, int e, int a, int b){
        if(s>=a&&e<=b)return tree[point];
        if(s>b||e<a)return {-llinf, -llinf, -llinf};
        int mid=(s+e)>>1;
        return query(point*2, s, mid, a, b)+query(point*2+1, mid+1, e, a, b);
    }
    LL query(int a, int b){
        return query(1, 1, n, a, b).ans;
    }
}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(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:90:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pv<poss.size()&&query[i].F.F<=poss[pv].F){
               ~~^~~~~~~~~~~~
jumps.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
jumps.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~~~
jumps.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
jumps.cpp:74: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