Submission #290072

#	Time	Username	Problem	Language	Result	Execution time	Memory
290072		balbit	Triple Jump (JOI19_jumps)	C++14	19 / 100	1286 ms	496184 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e5+5;

struct RMQ{
    int seg[2 * maxn];

    void build() {  // build the tree
      for (int i = maxn - 1; i > 0; --i) seg[i] = max(seg[i<<1] , seg[i<<1|1]);
    }

    void modify(int p, int value) {  // set value at position p
        for (seg[p += maxn] = value; p > 1; p >>= 1) seg[p>>1] = max(seg[p] , seg[p^1]);
    }

    int query(int l, int r) {  // sum on interval [l, r)
        int res = 0;
        for (l += maxn, r += maxn; l < r; l >>= 1, r >>= 1) {
            if (l&1) res = max(res, seg[l++]);
            if (r&1) res = max(res, seg[--r]);
        }
        return res;
    }
    RMQ(){
        memset(seg, 0, sizeof seg);
    }
};

int a[maxn];
struct EV{
    int l, r, v;
};

struct QUE{
    int l,r,i;
};

RMQ ar, dp;


struct QQ{
    int i, v, mx;
    bool operator < (const QQ &b) const {return i!=b.i?i<b.i:v>b.v;}
};

vector<QQ> here [maxn];
ll bg[maxn];

set<QQ> nowqq;

void upd(int i) {
    for (QQ x : here[i]) {
        // add x
        if (x.v > bg[x.i]) {
            bg[x.i] = x.v;
        }else continue;
        auto it = nowqq.insert(x).f;
        bug("HI");
        if (it != nowqq.begin() && prev(it)->v >= x.v) {
            nowqq.erase(it); continue;
        }
        if (it != nowqq.begin()) {
            dp.modify(prev(it)->i, prev(it) -> v + ar.query(prev(it)->i, x.i));
        }
        bug("HI");
        it = next(it);
        while (it->v <= x.v){
            dp.modify(it->i, 0);
            it = nowqq.erase(it);
        }
        bug("HI");
        x.mx = ar.query(x.i, it->i);
        dp.modify(x.i, x.v + x.mx);
        bug("HI");
    }
}

ll QU(int i) {
    auto fs = prev(nowqq.upper_bound({i, -1, 0}));
    ll re = ar.query(fs->i, i+1) + fs->v; // inclusive
    re = max(re, dp.query(0, fs->i));
    return re;
}

signed main(){
    IOS();

    int n; cin>>n;
    vector<EV> lines;
    {
        vector<pii> tt;
        for (int i = 0; i<n; ++i) {
            cin>>a[i]; tt.pb({-a[i],i}); ar.modify(i,a[i]);
        }

        sort(ALL(tt));
        set<int> tmps;
        for (auto & p : tt) {
            int i = p.s;
            auto it = tmps.insert(i).f;
            if (i != *tmps.rbegin()) {
                int j = *next(it);
                lines.pb({i, j + j-i, a[i] + a[j]});
            }
            if (i != *tmps.begin()) {
                int j = *prev(it);
                lines.pb({j, i + i-j, a[i] + a[j]});
            }
        }
//        return 0;
    }
    for (auto & l : lines) {bug(l.l, l.r, l.v);}
    lines.clear();
    for (int i = 0; i<n; ++i) for (int j = i+1; j<n; ++j) lines.pb({i,j-i+j,a[i] + a[j]});
    for (auto xx : lines) {
        if (xx.r < n)
            here[xx.l] . pb({xx.r, xx.v, -1});
    }
//    return 0;

    int numq; cin>>numq;
    vector<QUE> qlist;
    for (int i = 0; i<numq; ++i) {
        int l,r; cin>>l>>r;
        qlist.pb({l-1,r-1,i});
    }
    nowqq.insert({n,1000000000,0});
    sort(ALL(qlist),[&](QUE a, QUE b){return a.l > b.l;});
    int nowl = n;
    vector<int> ans(numq);
//    return 0;

    for (QUE q : qlist) {
        bug(q.l);
        while (nowl > q.l) {
            upd(--nowl);
        }
        ans[q.i] = QU(q.r);
    }
    for (int x : ans) {
        cout<<x<<endl;
    }
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:158:17: warning: unused variable 'l' [-Wunused-variable]
  158 |     for (auto & l : lines) {bug(l.l, l.r, l.v);}
      |                 ^

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