oj.uz

Submission #270460

# Submission time Handle Problem Language Result Execution time Memory
270460 2020-08-17T15:58:08 Z rqi Triple Jump (JOI19_jumps) C++14
100 / 100
 2692 ms 116232 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<bool> vb; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

template<class T> bool ckmin(T& a, const T& b) { 
    return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 
constexpr int pct(int x) { return __builtin_popcount(x); } 
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
ll half(ll x) { return fdiv(x,2); }

template<class T, class U> T fstTrue(T lo, T hi, U f) { 
    // note: if (lo+hi)/2 is used instead of half(lo+hi) then this will loop infinitely when lo=hi
    hi ++; assert(lo <= hi); // assuming f is increasing
    while (lo < hi) { // find first index such that f is true 
        T mid = half(lo+hi);
        f(mid) ? hi = mid : lo = mid+1; 
    } 
    return lo;
}
template<class T, class U> T lstTrue(T lo, T hi, U f) {
    lo --; assert(lo <= hi); // assuming f is decreasing
    while (lo < hi) { // find first index such that f is true 
        T mid = half(lo+hi+1);
        f(mid) ? lo = mid : hi = mid-1;
    } 
    return lo;
}
template<class T> void remDup(vector<T>& v) { 
    sort(all(v)); v.erase(unique(all(v)),end(v)); }

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) { 
    #ifdef LOCAL
        return b ? "true" : "false"; 
    #else 
        return ts((int)b);
    #endif
}
template<class A> str ts(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) {
    str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
    str res = ""; F0R(i,SZ) res += char('0'+b[i]);
    return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { // containers with begin(), end()
    #ifdef LOCAL
        bool fst = 1; str res = "{";
        for (const auto& x: v) {
            if (!fst) res += ", ";
            fst = 0; res += ts(x);
        }
        res += "}"; return res;
    #else
        bool fst = 1; str res = "";
        for (const auto& x: v) {
            if (!fst) res += " ";
            fst = 0; res += ts(x);
        }
        return res;

    #endif
}
template<class A, class B> str ts(pair<A,B> p) {
    #ifdef LOCAL
        return "("+ts(p.f)+", "+ts(p.s)+")"; 
    #else
        return ts(p.f)+" "+ts(p.s);
    #endif
}

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
    pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
    pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << ts(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
    #define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
    #define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
         << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
    #define dbg(...) 0
    #define chk(...) 0
#endif

// FILE I/O
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setIO(str s = "") {
    unsyncIO();
    // cin.exceptions(cin.failbit); 
    // throws exception when do smth illegal
    // ex. try to read letter into int
    if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

/**
 * Description: 1D range increment and sum query.
 * Source: USACO Counting Haybales
 * Verification: SPOJ Horrible
 */

template<int SZ> struct LazySeg { 
    static_assert(pct(SZ) == 1); // SZ must be power of 2
    const ll ID = -INF; 
    ll lazy[2*SZ];
    pl seg[2*SZ]; 
    ll maxval[2*SZ];

    LazySeg() {
        F0R(i,2*SZ){
            lazy[i] = ID;
            maxval[i] = 0;
            seg[i] = mp(0, ID);
        }
    }


    void push(int ind, int L, int R) { /// modify values for current node
        if(maxval[ind]+lazy[ind] >= seg[ind].f+seg[ind].s){
            seg[ind] = mp(maxval[ind], lazy[ind]);
        }
        if (L != R) F0R(i,2) ckmax(lazy[2*ind+i], lazy[ind]); /// prop to children
        lazy[ind] = ID; 
    } // recalc values for current node
    void pull(int ind) { 
        maxval[ind] = max(maxval[2*ind], maxval[2*ind+1]);
        if(seg[2*ind].f+seg[2*ind].s >= seg[2*ind+1].f+seg[2*ind+1].s){
            seg[ind] = seg[2*ind];
        }
        else seg[ind] = seg[2*ind+1];
    }
    void build(vl A) { 
        for(int i = 1; i < sz(A); i++){
            maxval[i+SZ] = A[i];
        }
        ROF(i,1,SZ) pull(i); 
    }     
    void upd(int lo,int hi,ll inc,int ind=1,int L=0, int R=SZ-1) {
        push(ind,L,R); if (hi < L || R < lo) return;
        if (lo <= L && R <= hi) { 
            lazy[ind] = inc; push(ind,L,R); return; }
        int M = (L+R)/2; upd(lo,hi,inc,2*ind,L,M); 
        upd(lo,hi,inc,2*ind+1,M+1,R); pull(ind);
    }
    ll query(int lo, int hi, int ind=1, int L=0, int R=SZ-1) {
        push(ind,L,R); if (lo > R || L > hi) return ID;
        if (lo <= L && R <= hi) return seg[ind].f+seg[ind].s;
        int M = (L+R)/2; 
        return max(query(lo,hi,2*ind,L,M),query(lo,hi,2*ind+1,M+1,R));
    }
};

const int mx = 500005;
int N;
ll A[mx];
int Q;
int L[mx];
int R[mx];
ll ans[mx];

LazySeg<524288> lseg;


int main() {
    setIO();
    cin >> N;
    set<int> inds;
    vpi vals;
    vl init;
    init.pb(0);
    for(int i = 1; i <= N; i++){
        cin >> A[i];
        vals.pb(mp(A[i], i));
        init.pb(A[i]);
    }
    lseg.build(init);

    sort(vals.rbegin(), vals.rend());
    vector<pair<pi, ll>> upds;
    for(auto u: vals){
        auto it = inds.lb(u.s);
        if(it != inds.end()){
            int ind = *it;
            upds.pb(mp(mp(u.s, 2*ind-u.s), A[u.s]+A[ind]));
        }
        if(it != inds.begin()){
            int ind = *(prev(it));
            upds.pb(mp(mp(ind, 2*u.s-ind), A[ind]+A[u.s]));
        }
        inds.ins(u.s);
    }
    sort(upds.rbegin(), upds.rend());

    cin >> Q;
    vpi queries;
    for(int i = 1; i <= Q; i++){
        cin >> L[i] >> R[i];
        queries.pb(mp(L[i], i));
    }
    sort(queries.rbegin(), queries.rend());
    int curupd = 0;
    for(auto u: queries){
        int qL = L[u.s];
        int qR = R[u.s];
        while(curupd < sz(upds)){
            if(upds[curupd].f.s > N){
                curupd++;
                continue;
            }
            if(upds[curupd].f.f < qL){
                break;
            }
            int l = upds[curupd].f.s;
            lseg.upd(l, N, upds[curupd].s);
            curupd++;
        }
        ans[u.s] = lseg.query(qL, qR);
    }

    for(int i = 1; i <= Q; i++){
        ps(ans[i]);
    }
    // you should actually read the stuff at the bottom
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    * do smth instead of nothing and stay organized
    * WRITE STUFF DOWN
*/

Compilation message

jumps.cpp: In function 'void setIn(str)':
jumps.cpp:168:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  168 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void setOut(str)':
jumps.cpp:169:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  169 | void setOut(str s) { freopen(s.c_str(),"w",stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33152 KB Output is correct
2 Correct 24 ms 33272 KB Output is correct
3 Correct 24 ms 33152 KB Output is correct
4 Correct 25 ms 33152 KB Output is correct
5 Correct 25 ms 33152 KB Output is correct
6 Correct 24 ms 33152 KB Output is correct
7 Correct 24 ms 33152 KB Output is correct
8 Correct 25 ms 33280 KB Output is correct
9 Correct 24 ms 33152 KB Output is correct
10 Correct 24 ms 33152 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33152 KB Output is correct
2 Correct 24 ms 33272 KB Output is correct
3 Correct 24 ms 33152 KB Output is correct
4 Correct 25 ms 33152 KB Output is correct
5 Correct 25 ms 33152 KB Output is correct
6 Correct 24 ms 33152 KB Output is correct
7 Correct 24 ms 33152 KB Output is correct
8 Correct 25 ms 33280 KB Output is correct
9 Correct 24 ms 33152 KB Output is correct
10 Correct 24 ms 33152 KB Output is correct
11 Correct 590 ms 55392 KB Output is correct
12 Correct 594 ms 55284 KB Output is correct
13 Correct 583 ms 55252 KB Output is correct
14 Correct 596 ms 55560 KB Output is correct
15 Correct 593 ms 55392 KB Output is correct
16 Correct 613 ms 54708 KB Output is correct
17 Correct 616 ms 54568 KB Output is correct
18 Correct 603 ms 54620 KB Output is correct
19 Correct 599 ms 55412 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 55336 KB Output is correct
2 Correct 277 ms 52256 KB Output is correct
3 Correct 274 ms 52268 KB Output is correct
4 Correct 586 ms 55464 KB Output is correct
5 Correct 597 ms 55332 KB Output is correct
6 Correct 532 ms 54600 KB Output is correct
7 Correct 520 ms 54568 KB Output is correct
8 Correct 530 ms 54572 KB Output is correct
9 Correct 539 ms 54952 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33152 KB Output is correct
2 Correct 24 ms 33272 KB Output is correct
3 Correct 24 ms 33152 KB Output is correct
4 Correct 25 ms 33152 KB Output is correct
5 Correct 25 ms 33152 KB Output is correct
6 Correct 24 ms 33152 KB Output is correct
7 Correct 24 ms 33152 KB Output is correct
8 Correct 25 ms 33280 KB Output is correct
9 Correct 24 ms 33152 KB Output is correct
10 Correct 24 ms 33152 KB Output is correct
11 Correct 590 ms 55392 KB Output is correct
12 Correct 594 ms 55284 KB Output is correct
13 Correct 583 ms 55252 KB Output is correct
14 Correct 596 ms 55560 KB Output is correct
15 Correct 593 ms 55392 KB Output is correct
16 Correct 613 ms 54708 KB Output is correct
17 Correct 616 ms 54568 KB Output is correct
18 Correct 603 ms 54620 KB Output is correct
19 Correct 599 ms 55412 KB Output is correct
20 Correct 576 ms 55336 KB Output is correct
21 Correct 277 ms 52256 KB Output is correct
22 Correct 274 ms 52268 KB Output is correct
23 Correct 586 ms 55464 KB Output is correct
24 Correct 597 ms 55332 KB Output is correct
25 Correct 532 ms 54600 KB Output is correct
26 Correct 520 ms 54568 KB Output is correct
27 Correct 530 ms 54572 KB Output is correct
28 Correct 539 ms 54952 KB Output is correct
29 Correct 2692 ms 116084 KB Output is correct
30 Correct 1618 ms 108168 KB Output is correct
31 Correct 1625 ms 108312 KB Output is correct
32 Correct 2552 ms 115940 KB Output is correct
33 Correct 2566 ms 115956 KB Output is correct
34 Correct 2409 ms 113636 KB Output is correct
35 Correct 2406 ms 113432 KB Output is correct
36 Correct 2424 ms 113312 KB Output is correct
37 Correct 2323 ms 114916 KB Output is correct
38 Correct 2100 ms 116176 KB Output is correct
39 Correct 2158 ms 116132 KB Output is correct
40 Correct 1911 ms 112768 KB Output is correct
41 Correct 1894 ms 112088 KB Output is correct
42 Correct 1975 ms 112276 KB Output is correct
43 Correct 1993 ms 114028 KB Output is correct
44 Correct 2198 ms 116204 KB Output is correct
45 Correct 2153 ms 116056 KB Output is correct
46 Correct 1967 ms 112796 KB Output is correct
47 Correct 2109 ms 112572 KB Output is correct
48 Correct 1990 ms 112832 KB Output is correct
49 Correct 1964 ms 114540 KB Output is correct
50 Correct 2296 ms 116232 KB Output is correct
51 Correct 2440 ms 116064 KB Output is correct
52 Correct 2060 ms 113636 KB Output is correct
53 Correct 2083 ms 113324 KB Output is correct
54 Correct 2059 ms 113308 KB Output is correct
55 Correct 2139 ms 115424 KB Output is correct