oj.uz

Submission #284081

# Submission time Handle Problem Language Result Execution time Memory
284081 2020-08-26T17:08:19 Z aloo123 Triple Jump (JOI19_jumps) C++14
100 / 100
 2617 ms 116356 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:32: 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:33: 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 24 ms 33272 KB Output is correct
2 Correct 24 ms 33152 KB Output is correct
3 Correct 24 ms 33280 KB Output is correct
4 Correct 24 ms 33280 KB Output is correct
5 Correct 24 ms 33152 KB Output is correct
6 Correct 24 ms 33272 KB Output is correct
7 Correct 25 ms 33280 KB Output is correct
8 Correct 24 ms 33152 KB Output is correct
9 Correct 24 ms 33144 KB Output is correct
10 Correct 24 ms 33280 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33272 KB Output is correct
2 Correct 24 ms 33152 KB Output is correct
3 Correct 24 ms 33280 KB Output is correct
4 Correct 24 ms 33280 KB Output is correct
5 Correct 24 ms 33152 KB Output is correct
6 Correct 24 ms 33272 KB Output is correct
7 Correct 25 ms 33280 KB Output is correct
8 Correct 24 ms 33152 KB Output is correct
9 Correct 24 ms 33144 KB Output is correct
10 Correct 24 ms 33280 KB Output is correct
11 Correct 591 ms 55556 KB Output is correct
12 Correct 589 ms 55260 KB Output is correct
13 Correct 589 ms 55316 KB Output is correct
14 Correct 603 ms 55388 KB Output is correct
15 Correct 607 ms 55392 KB Output is correct
16 Correct 599 ms 54712 KB Output is correct
17 Correct 610 ms 54624 KB Output is correct
18 Correct 612 ms 54684 KB Output is correct
19 Correct 626 ms 55296 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 285 ms 52272 KB Output is correct
3 Correct 278 ms 52268 KB Output is correct
4 Correct 569 ms 55480 KB Output is correct
5 Correct 590 ms 55332 KB Output is correct
6 Correct 528 ms 54680 KB Output is correct
7 Correct 527 ms 54572 KB Output is correct
8 Correct 528 ms 54688 KB Output is correct
9 Correct 519 ms 54952 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33272 KB Output is correct
2 Correct 24 ms 33152 KB Output is correct
3 Correct 24 ms 33280 KB Output is correct
4 Correct 24 ms 33280 KB Output is correct
5 Correct 24 ms 33152 KB Output is correct
6 Correct 24 ms 33272 KB Output is correct
7 Correct 25 ms 33280 KB Output is correct
8 Correct 24 ms 33152 KB Output is correct
9 Correct 24 ms 33144 KB Output is correct
10 Correct 24 ms 33280 KB Output is correct
11 Correct 591 ms 55556 KB Output is correct
12 Correct 589 ms 55260 KB Output is correct
13 Correct 589 ms 55316 KB Output is correct
14 Correct 603 ms 55388 KB Output is correct
15 Correct 607 ms 55392 KB Output is correct
16 Correct 599 ms 54712 KB Output is correct
17 Correct 610 ms 54624 KB Output is correct
18 Correct 612 ms 54684 KB Output is correct
19 Correct 626 ms 55296 KB Output is correct
20 Correct 576 ms 55336 KB Output is correct
21 Correct 285 ms 52272 KB Output is correct
22 Correct 278 ms 52268 KB Output is correct
23 Correct 569 ms 55480 KB Output is correct
24 Correct 590 ms 55332 KB Output is correct
25 Correct 528 ms 54680 KB Output is correct
26 Correct 527 ms 54572 KB Output is correct
27 Correct 528 ms 54688 KB Output is correct
28 Correct 519 ms 54952 KB Output is correct
29 Correct 2557 ms 116036 KB Output is correct
30 Correct 1647 ms 108232 KB Output is correct
31 Correct 1609 ms 108152 KB Output is correct
32 Correct 2617 ms 116216 KB Output is correct
33 Correct 2609 ms 115980 KB Output is correct
34 Correct 2395 ms 113796 KB Output is correct
35 Correct 2402 ms 113336 KB Output is correct
36 Correct 2391 ms 113512 KB Output is correct
37 Correct 2423 ms 114924 KB Output is correct
38 Correct 2143 ms 116196 KB Output is correct
39 Correct 2130 ms 116140 KB Output is correct
40 Correct 1904 ms 112740 KB Output is correct
41 Correct 1908 ms 112216 KB Output is correct
42 Correct 1950 ms 112340 KB Output is correct
43 Correct 1944 ms 114016 KB Output is correct
44 Correct 2189 ms 116280 KB Output is correct
45 Correct 2183 ms 116244 KB Output is correct
46 Correct 2037 ms 113024 KB Output is correct
47 Correct 2000 ms 112724 KB Output is correct
48 Correct 2007 ms 112504 KB Output is correct
49 Correct 2001 ms 114728 KB Output is correct
50 Correct 2274 ms 116356 KB Output is correct
51 Correct 2277 ms 116064 KB Output is correct
52 Correct 2107 ms 113880 KB Output is correct
53 Correct 2098 ms 113440 KB Output is correct
54 Correct 2079 ms 113604 KB Output is correct
55 Correct 2106 ms 115036 KB Output is correct