oj.uz

Submission #290072

# Submission time Handle Problem Language Result Execution time Memory
290072 2020-09-03T11:14:04 Z balbit Triple Jump (JOI19_jumps) C++14
19 / 100
 1286 ms 496184 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 = 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5888 KB Output is correct
2 Correct 4 ms 6144 KB Output is correct
3 Correct 5 ms 6144 KB Output is correct
4 Correct 4 ms 6144 KB Output is correct
5 Correct 4 ms 6144 KB Output is correct
6 Correct 6 ms 6144 KB Output is correct
7 Correct 4 ms 6144 KB Output is correct
8 Correct 4 ms 6144 KB Output is correct
9 Correct 4 ms 6144 KB Output is correct
10 Correct 5 ms 6144 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5888 KB Output is correct
2 Correct 4 ms 6144 KB Output is correct
3 Correct 5 ms 6144 KB Output is correct
4 Correct 4 ms 6144 KB Output is correct
5 Correct 4 ms 6144 KB Output is correct
6 Correct 6 ms 6144 KB Output is correct
7 Correct 4 ms 6144 KB Output is correct
8 Correct 4 ms 6144 KB Output is correct
9 Correct 4 ms 6144 KB Output is correct
10 Correct 5 ms 6144 KB Output is correct
11 Correct 960 ms 496184 KB Output is correct
12 Correct 1010 ms 495904 KB Output is correct
13 Correct 1286 ms 496020 KB Output is correct
14 Correct 953 ms 496144 KB Output is correct
15 Correct 968 ms 496180 KB Output is correct
16 Correct 962 ms 495628 KB Output is correct
17 Correct 953 ms 495500 KB Output is correct
18 Correct 961 ms 495528 KB Output is correct
19 Correct 969 ms 496068 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 17644 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5888 KB Output is correct
2 Correct 4 ms 6144 KB Output is correct
3 Correct 5 ms 6144 KB Output is correct
4 Correct 4 ms 6144 KB Output is correct
5 Correct 4 ms 6144 KB Output is correct
6 Correct 6 ms 6144 KB Output is correct
7 Correct 4 ms 6144 KB Output is correct
8 Correct 4 ms 6144 KB Output is correct
9 Correct 4 ms 6144 KB Output is correct
10 Correct 5 ms 6144 KB Output is correct
11 Correct 960 ms 496184 KB Output is correct
12 Correct 1010 ms 495904 KB Output is correct
13 Correct 1286 ms 496020 KB Output is correct
14 Correct 953 ms 496144 KB Output is correct
15 Correct 968 ms 496180 KB Output is correct
16 Correct 962 ms 495628 KB Output is correct
17 Correct 953 ms 495500 KB Output is correct
18 Correct 961 ms 495528 KB Output is correct
19 Correct 969 ms 496068 KB Output is correct
20 Runtime error 32 ms 17644 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -