Submission #589744

#	Time	Username	Problem	Language	Result	Execution time	Memory
589744		Huy	Triple Jump (JOI19_jumps)	C++17	100 / 100	906 ms	84572 KiB

jumps

/// no sound bitch
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,ll>
#define fi first
#define se second
/*#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")*/
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ldb = long double;
const ll N = (int)1e9 + 1;
const int maxN = (int)5e5 + 1;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll infty = 1e18 + 7;
const int base = (int)4e5;

void InputFile()
{
    //freopen("scrivener.inp","r",stdin);
    //freopen("scrivener.out","w",stdout);
    //freopen("test.out","r",stdin);
}

void FastInput()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

struct TQuery
{
    int lf,rt,id;
};
vector<TQuery> save_query;

bool FQ(TQuery x,TQuery y)
{
    return x.lf > y.lf;
}

int n;
int q;
int a[maxN];
vector<pii> req;
int res[maxN];

struct Node
{
    int max_a;
    int lazy;
    int val;
};

Node ST[4*maxN];

void Build(int id,int l,int r)
{
    if(l == r)
    {
        ST[id].max_a = ST[id].val = a[l];
        ST[id].lazy = 0;
        return;
    }
    int mid = (l + r) / 2;
    Build(id * 2,l,mid);
    Build(id * 2 + 1,mid + 1,r);
    ST[id].max_a = ST[id].val = max(ST[id*2].max_a,ST[id*2+1].max_a);
    ST[id].lazy = 0;
}

void Down(int id)
{
    if(!ST[id].lazy) return;
    ST[id*2].val = max(ST[id*2].val,ST[id*2].max_a + ST[id].lazy);
    ST[id*2].lazy = max(ST[id*2].lazy,ST[id].lazy);
    ST[id*2+1].val = max(ST[id*2+1].val,ST[id*2+1].max_a + ST[id].lazy);
    ST[id*2+1].lazy = max(ST[id*2+1].lazy,ST[id].lazy);
    ST[id].lazy = 0;
}

void Update(int id,int l,int r,int u,int v,int n_val)
{
    if(v < l || u > r) return;
    if(u <= l && r <= v)
    {
        ST[id].val = max(ST[id].val,ST[id].max_a + n_val);
        ST[id].lazy = max(ST[id].lazy,n_val);
        return;
    }
    Down(id);
    int mid = (l + r) / 2;
    Update(id * 2,l,mid,u,v,n_val);
    Update(id * 2 + 1,mid + 1,r,u,v,n_val);
    ST[id].val = max(ST[id*2].val,ST[id*2+1].val);
}

int Get(int id,int l,int r,int u,int v)
{
    if(v < l || u > r) return -infty;
    if(u <= l && r <= v)
    {
        return ST[id].val;
    }
    Down(id);
    int mid = (l + r) / 2;
    return max(Get(id * 2,l,mid,u,v),Get(id * 2 + 1,mid + 1,r,u,v));
}

void Read()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    cin >> q;
    for(int i = 1;i <= q;i++)
    {
        int l,r;
        cin >> l >> r;
        save_query.push_back({l,r,i});
    }
}

void Solve()
{
    //cout <<"dark";return;
    vector<int> vc;
    for(int i = n;i >= 1;i--)
    {
        if(vc.empty()) vc.push_back(i);
        else
        {
            while(!vc.empty() && a[vc.back()] < a[i])
            {
                req.push_back({i,vc.back()});
                vc.pop_back();
            }
            if(!vc.empty()) req.push_back({i,vc.back()});
            vc.push_back(i);
        }
    }
    sort(req.begin(),req.end(),greater<pii>());
    sort(save_query.begin(),save_query.end(),FQ);
    /*for(pii tmp : req)
    {
        cout <<'*'<<' '<< tmp.fi <<' '<< tmp.se <<'\n';
    }
    return;*/
    Build(1,1,n);
    int pt = 0;
    for(TQuery tmp : save_query)
    {
        while(pt < req.size() && req[pt].fi >= tmp.lf)
        {
            if(2 * req[pt].se - req[pt].fi <= n)
            {
                Update(1,1,n,2*req[pt].se-req[pt].fi,n,a[req[pt].fi]+a[req[pt].se]);
            }
            pt++;
        }
        res[tmp.id] = Get(1,1,n,tmp.lf+2,tmp.rt);
    }
    for(int i = 1;i <= q;i++)
    {
        cout << res[i] <<'\n';
    }
}

void Debug()
{

}


int32_t main()
{
    FastInput();
    //InputFile();
    //int sub_type;
    //cin >> sub_type;
    //Sieve();
    //Prepare();
    int test;
    //cin >> test;
    test = 1;
    while(test--)
        //for(int prc = 1; prc <= test; prc++)
    {
        Read();
        Solve();
        //Debug();
    }
}

Compilation message (stderr)

jumps.cpp: In function 'void Solve()':
jumps.cpp:160:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         while(pt < req.size() && req[pt].fi >= tmp.lf)
      |               ~~~^~~~~~~~~~~~

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