oj.uz

Submission #290075

# Submission time Handle Problem Language Result Execution time Memory
290075 2020-09-03T11:16:21 Z balbit Triple Jump (JOI19_jumps) C++14
100 / 100
 1574 ms 131992 KB 
#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 = 5e5+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;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27900 KB Output is correct
2 Correct 18 ms 27776 KB Output is correct
3 Correct 18 ms 27776 KB Output is correct
4 Correct 20 ms 27776 KB Output is correct
5 Correct 17 ms 27776 KB Output is correct
6 Correct 20 ms 27776 KB Output is correct
7 Correct 18 ms 27776 KB Output is correct
8 Correct 18 ms 27776 KB Output is correct
9 Correct 18 ms 27776 KB Output is correct
10 Correct 18 ms 27776 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27900 KB Output is correct
2 Correct 18 ms 27776 KB Output is correct
3 Correct 18 ms 27776 KB Output is correct
4 Correct 20 ms 27776 KB Output is correct
5 Correct 17 ms 27776 KB Output is correct
6 Correct 20 ms 27776 KB Output is correct
7 Correct 18 ms 27776 KB Output is correct
8 Correct 18 ms 27776 KB Output is correct
9 Correct 18 ms 27776 KB Output is correct
10 Correct 18 ms 27776 KB Output is correct
11 Correct 278 ms 49468 KB Output is correct
12 Correct 302 ms 49496 KB Output is correct
13 Correct 270 ms 49112 KB Output is correct
14 Correct 279 ms 49288 KB Output is correct
15 Correct 261 ms 49420 KB Output is correct
16 Correct 260 ms 48652 KB Output is correct
17 Correct 263 ms 48632 KB Output is correct
18 Correct 255 ms 48652 KB Output is correct
19 Correct 262 ms 49036 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 54404 KB Output is correct
2 Correct 170 ms 56084 KB Output is correct
3 Correct 147 ms 48252 KB Output is correct
4 Correct 411 ms 55072 KB Output is correct
5 Correct 418 ms 55300 KB Output is correct
6 Correct 307 ms 54404 KB Output is correct
7 Correct 317 ms 54276 KB Output is correct
8 Correct 315 ms 54352 KB Output is correct
9 Correct 308 ms 54660 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27900 KB Output is correct
2 Correct 18 ms 27776 KB Output is correct
3 Correct 18 ms 27776 KB Output is correct
4 Correct 20 ms 27776 KB Output is correct
5 Correct 17 ms 27776 KB Output is correct
6 Correct 20 ms 27776 KB Output is correct
7 Correct 18 ms 27776 KB Output is correct
8 Correct 18 ms 27776 KB Output is correct
9 Correct 18 ms 27776 KB Output is correct
10 Correct 18 ms 27776 KB Output is correct
11 Correct 278 ms 49468 KB Output is correct
12 Correct 302 ms 49496 KB Output is correct
13 Correct 270 ms 49112 KB Output is correct
14 Correct 279 ms 49288 KB Output is correct
15 Correct 261 ms 49420 KB Output is correct
16 Correct 260 ms 48652 KB Output is correct
17 Correct 263 ms 48632 KB Output is correct
18 Correct 255 ms 48652 KB Output is correct
19 Correct 262 ms 49036 KB Output is correct
20 Correct 411 ms 54404 KB Output is correct
21 Correct 170 ms 56084 KB Output is correct
22 Correct 147 ms 48252 KB Output is correct
23 Correct 411 ms 55072 KB Output is correct
24 Correct 418 ms 55300 KB Output is correct
25 Correct 307 ms 54404 KB Output is correct
26 Correct 317 ms 54276 KB Output is correct
27 Correct 315 ms 54352 KB Output is correct
28 Correct 308 ms 54660 KB Output is correct
29 Correct 1566 ms 131724 KB Output is correct
30 Correct 1326 ms 125992 KB Output is correct
31 Correct 750 ms 104644 KB Output is correct
32 Correct 1574 ms 131808 KB Output is correct
33 Correct 1569 ms 131820 KB Output is correct
34 Correct 1260 ms 129632 KB Output is correct
35 Correct 1265 ms 129168 KB Output is correct
36 Correct 1259 ms 129340 KB Output is correct
37 Correct 1273 ms 130828 KB Output is correct
38 Correct 1504 ms 131992 KB Output is correct
39 Correct 1482 ms 131856 KB Output is correct
40 Correct 1150 ms 128520 KB Output is correct
41 Correct 1188 ms 128208 KB Output is correct
42 Correct 1166 ms 128052 KB Output is correct
43 Correct 1178 ms 129804 KB Output is correct
44 Correct 1468 ms 131876 KB Output is correct
45 Correct 1471 ms 131884 KB Output is correct
46 Correct 1151 ms 128780 KB Output is correct
47 Correct 1151 ms 128268 KB Output is correct
48 Correct 1148 ms 128276 KB Output is correct
49 Correct 1190 ms 130388 KB Output is correct
50 Correct 1496 ms 131852 KB Output is correct
51 Correct 1508 ms 131912 KB Output is correct
52 Correct 1177 ms 129740 KB Output is correct
53 Correct 1189 ms 129012 KB Output is correct
54 Correct 1208 ms 129136 KB Output is correct
55 Correct 1192 ms 130716 KB Output is correct