Submission #1175368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175368		pinruei	Triple Jump (JOI19_jumps)	C++20	0 / 100	152 ms	39052 KiB

jumps

#pragma region//         
#include<bits/stdc++.h>
#define int long long
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#define f2(i, m) for(int i=0; i<m; i++)
#define f21(i, m) for(int i=1; i<m; i++)
#define f3(i, n, m) for(int i=n; i<m; i++)
#define f2_(i, m) for(int i=m; i>-1; i--)
#define f21_(i, m) for(int i=m; i>0; i--)
#define f3_(i, n, m) for(int i=n; i>=m; i--)
#define travG(idx) for(int i : g[idx])
#define travG_(i, idx) for(int i : g[idx])
#define trav(loop) for(int i : loop)
#define trav_(i, loop) for(int i : loop)
#define trav2(loop, idx) for(int i : loop[idx])
#define trav2_(i, loop, idx) for(int i : loop[idx])
#define ll long long
#define bs bitset
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define ve vector<element>
#define ve_ vector<element_>
#define vpii vector<pair<int, int>>
#define qi queue<int>
#define qe queue<element>
#define qpii queue<pair<int, int>>
#define si stack<int>
#define se stack<element>
#define spii stack<pair<int, int>>
#define vb vector<bool>
#define pqi priority_queue<int>
#define pqi_ priority_queue<int, vi, greater<int>>
#define pqpii priority_queue<pair<int, int>>
#define pqpii_ priority_queue<pair<int, int>, vpii, greater<pii>>
#define pb push_back
#define pf push_front
#define pob pop_back()
#define pof pop_front()
#define len length()
#define elif else if
#define mod 1000000007
#pragma endregion
//#define debug
/*
#ifdef debug
#endif
#ifndef debug
#endif
*/
using namespace std;

constexpr bool debug = 0;
constexpr int mxn=5e5+1, mxq=5e5+1;
int n, q, c[mxn];
vi cor[mxn];

struct SEG
{
    int curL;


    // a + b -> maintain by vpii{a+b, l}
    vpii ab;


    // a + b + c
    /*
    function:
        range query max
        range update add
    */
    vector<int> tree, tag;


    int qu(int idx, int l, int r, int ql, int qr)
    {
        if(ql>r || qr<l) return 0;
        if(ql<=l && r<=qr) return tree[idx];
        
        {   // lazy transfer
            tag[idx<<1]+=tag[idx], tag[idx<<1|1]+=tag[idx];
            tree[idx<<1]+=tag[idx], tree[idx<<1|1]+=tag[idx], tag[idx]=0;
        }

        int m = l+r>>1;
        return max(qu(idx<<1, l, m, ql, qr), qu(idx<<1|1, m+1, r, ql, qr));
    }
    void build(int idx, int l, int r)
    {
        if(l==r)
        {
            tree[idx]=c[l];
            return;
        }
        int m = l+r>>1;
        build(idx<<1, l, m), build(idx<<1|1, m+1, r);
        tree[idx] = max(tree[idx<<1], tree[idx<<1|1]);
    }
    void ud(int idx, int l, int r, int ql, int qr, int v)
    {
        if(ql>r || qr<l) return;
        if(ql<=l && r<=qr)
        {
            tree[idx]+=v;
            tag[idx]+=v;
            return;
        }

        {   // lazy transfer
            tag[idx<<1]+=tag[idx], tag[idx<<1|1]+=tag[idx];
            tree[idx<<1]+=tag[idx], tree[idx<<1|1]+=tag[idx], tag[idx]=0;
        }
        
        int m = l+r>>1;
        ud(idx<<1, l, m, ql, qr, v), ud(idx<<1|1, m+1, r, ql, qr, v);
        tree[idx] = max(tree[idx<<1], tree[idx<<1|1]);
    }

    void init_L(int l)
    {
        f3_(i, curL, l)
        {
            for(int j : cor[i])
            {
                // for each element in range [2j-i, n-1] can be updated
                
                if((j<<1)-i>=n) continue; // out of array
                
                if(debug)
                {
                    cout<<"init: "<<i<<' '<<j<<'\n';
                }
                

                int value = c[i]+c[j];
                auto rPtr = upper_bound(begin(ab), end(ab), pii{value, 0});
                if(rPtr->second<(j<<1)-i && rPtr!=end(ab)) // needless to be updated
                    continue;
                
                int r = (rPtr==end(ab) ? n-1 : rPtr->second-1);
                while(1)
                {
                    rPtr--;
                    ud(1, 0, n-1, max(rPtr->second, (j<<1)-i), r, value-rPtr->first);
                    r = rPtr->second-1;
                    if(r>=(j<<1)-i-1)
                    {
                        ab.erase(rPtr);
                        if(r==(j<<1)-i-1) break;
                    }
                    else break;
                }
                ab.insert(rPtr+1, {value, (j<<1)-i});

                if(debug)
                {
                    cout << "\n\n";
                    for(auto i : ab) cout << '{'<<i.first << ", " << i.second << "} ";
                    cout << "\n\n";
                }
            }
        }
        curL = l-1;
    }
    void init()
    {
        ab.pb({0, 0});
        tree.resize(n<<2);
        tag.resize(n<<2);
        build(1, 0, n-1); 
        curL = n-1;
    }
}seg;


signed main()//         https://oj.uz/problem/view/IOI08_printer
{   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    // input
    {
        si stk;
        int tmp[mxn];
        cin >> n;
        f2(i, n)
        {
            int t; cin>>t;
            c[i] = t;
            while(!stk.empty() && c[i]>c[stk.top()])
                stk.pop();
            tmp[i] = stk.empty()?-1:stk.top();
            stk.push(i);
            if(i!=n-1) cor[i].pb(i+1);
        }

        while(!stk.empty()) stk.pop();
        f2_(i, n-1)
        {
            if(tmp[i]==-1)
            {
                stk.push(i);
                continue;
            }
            while(!stk.empty() && c[i]>c[stk.top()])
                stk.pop();
            if(stk.empty())
            {
                stk.push(i);
                continue;
            }
            cor[tmp[i]].pb(stk.top());
            
            
            if(debug) 
            {
                cout<<tmp[i]<<' '<<stk.top()<<'\n';
            }


            stk.push(i);
        }
    }


    // query and output
    {
        cin >> q;
        struct output
        {
            int l, r, idx;
        };
        output query[q];
        int ans[q];

        int t=0;
        for(output &i : query) cin>>i.l>>i.r, i.idx=t++;
        sort(query, query+q, [&](output a, output b)
        {
            return a.l>b.l;
        });

        seg.init();
        for(output i : query)
        {
            seg.init_L(i.l-1);
            ans[i.idx] = seg.qu(1, 0, n-1, i.l+1, i.r-1);
        }
        for(int i:ans) cout<<i<<'\n';
    }
    return 0;
}

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