Submission #200920

#	Time	Username	Problem	Language	Result	Execution time	Memory
200920		mhy908	Triple Jump (JOI19_jumps)	C++14	100 / 100	3146 ms	71212 KiB

jumps

#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{
        int st, fin;
        LL f, arr, ans;
    }tree[2000000];
    void init(int point, int num){
        if(num==1)tree[point].st=tree[point].fin=++x;
        if(num<=1)return;
        init(point*2, num-num/2);
        init(point*2+1, num/2);
        tree[point].st=tree[point*2].st;
        tree[point].fin=tree[point*2+1].fin;
    }
    void update_arr(int point, int num, LL qu){
        if(tree[point].st==tree[point].fin){
            tree[point].arr=qu;
            tree[point].ans=tree[point].arr+tree[point].f;
            return;
        }
        if(num<=tree[point*2].fin)update_arr(point*2, num, qu);
        else update_arr(point*2+1, 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 num, LL qu){
        if(tree[point].st==tree[point].fin){
            tree[point].f=max(tree[point].f, qu);
            tree[point].ans=tree[point].arr+tree[point].f;
            return;
        }
        if(num<=tree[point*2].fin)update_f(point*2, num, qu);
        else update_f(point*2+1, 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 a, int b){
        if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].arr;
        if(tree[point].st>b||tree[point].fin<a)return -llinf;
        return max(query_arr(point*2, a, b), query_arr(point*2+1, a, b));
    }
    LL query_f(int point, int a, int b){
        if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].f;
        if(tree[point].st>b||tree[point].fin<a)return -llinf;
        return max(query_f(point*2, a, b), query_f(point*2+1, a, b));
    }
    LL query(int point, int a, int b){
        if(tree[point].st>=a&&tree[point].fin<=b)return tree[point].ans;
        if(tree[point].st>b||tree[point].fin<a)return -llinf;
        return max(max(query(point*2, a, b), query(point*2+1, a, b)), query_f(point*2, a, b)+query_arr(point*2+1, a, b));
    }
}seg;

int main(){
    scanf("%d", &n);
    seg.init(1, n);
    for(int i=1; i<=n; i++){
        scanf("%lld", &arr[i]);
        seg.update_arr(1, 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, 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, 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:103:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pv<poss.size()&&query[i].F.F<=poss[pv].F){
               ~~^~~~~~~~~~~~
jumps.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
jumps.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~~~
jumps.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
jumps.cpp:87: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