oj.uz

Submission #365902

# Submission time Handle Problem Language Result Execution time Memory
365902 2021-02-12T13:46:46 Z ACmachine Triple Jump (JOI19_jumps) C++17
100 / 100
 1603 ms 119888 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<str> vstr;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define rsz resize 
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
	
const double EPS = 1e-9;
const int MOD = 1e9+7; // 998244353;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

#ifdef DEBUG
#define DBG if(1)
#else
#define DBG if(0)
#endif

#define dbg(x) cout << "(" << #x << " : " << x << ")" << endl;
// ostreams
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }
//searches
template<typename T, typename U>
T bsl(T lo, T hi, U f){ hi++; T mid; while(lo < hi){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; }
template<typename U>
double bsld(double lo, double hi, U f, double p = 1e-9){ int r = 3 + (int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid; } return (lo + hi)/2; }
template<typename T, typename U>
T bsh(T lo, T hi, U f){ lo--; T mid; while(lo < hi){ mid = (lo + hi + 1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }
template<typename U>
double bshd(double lo, double hi, U f, double p = 1e-9){ int r = 3+(int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? lo = mid : hi = mid; } return (lo + hi)/2; }
// some more utility functions
template<typename T>
pair<T, int> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return mp(*it, it - v.begin());}
template<typename T>
pair<T, int> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return mp(*it, it - v.begin());}        
template<typename T> bool ckmin(T& a, const T& b){return b < a ? a = b , true : false;}
template<typename T> bool ckmax(T& a, const T& b){return b > a ? a = b, true : false;}

struct node{
    ll fval = 0, val = 0, lazy = 0;
    void apply(int l, int r, ll valu){
        fval = max(fval, val + valu); 
        lazy = max(lazy, valu);
    }
};
struct segtree{
    node comb(node const &a, node const &b){
        node res;
        res.fval = max(a.fval, b.fval);
        res.val = max(a.val, b.val);
        return res;
    } 
    void push(int l, int r, int v){
        tree[v<<1].lazy = max(tree[v<<1].lazy, tree[v].lazy);
        tree[v<<1].fval = max(tree[v<<1].fval, tree[v<<1].val + tree[v<<1].lazy);
        tree[v<<1|1].lazy = max(tree[v<<1|1].lazy, tree[v].lazy);
        tree[v<<1|1].fval = max(tree[v<<1|1].fval, tree[v<<1|1].val + tree[v<<1|1].lazy);
    }
    int sz;
    vector<node> tree; 
    segtree(int _sz){ // tree is resized to default values set in node
        sz = 1; while(sz < _sz) sz<<=1;
        tree.resize(2*sz); 
    } 
    void build(vector<node> &init){
        for(int i = 0; i < sz; ++i) 
            if(i < init.size())
                tree[i+sz] = init[i];
        for(int i = sz-1; i > 0; --i)
            tree[i] = comb(tree[i<<1], tree[i<<1|1]);
    } 
    node query(int l, int r){return query0(l, r, 0, sz, 1);} 
    node query0(int l, int r, int beg, int end, int v){ 
        if(beg >= l && end <= r)
            return tree[v];
        push(beg, end, v);
        int mid = (beg + end) >> 1;
        node res;
        if(beg >= r || mid <= l) res = query0(l, r, mid, end, v<<1|1); //[beg, mid]
        else if(mid >= r || end <= l) res = query0(l, r, beg, mid, v<<1);
        else res = comb(query0(l, r, beg, mid, v<<1), query0(l, r, mid, end, v<<1|1));
        return res;
    } 
    template<typename... T>
    void upd(int l, int r, T ...args){upd0(l, r, 0, sz, 1, args...);}
    template<typename... T>
    void upd0(int l, int r, int beg, int end, int v, T ...args){
        if(beg >= r || end <= l)
            return;
        if(beg >= l && end <= r){
            tree[v].apply(beg, end, args...);
            return;
        }
        push(beg, end, v);
        int mid = (beg + end) >> 1;
        upd0(l, r, beg, mid, v<<1, args...);
        upd0(l, r, mid, end, v<<1|1, args...);
        tree[v] = comb(tree[v<<1], tree[v<<1|1]);
    } 
};

    
int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
	int n; cin >> n;
    vi a(n); cin >> a;
    vector<array<int, 2>> iv;
    stack<array<int, 2>> stk;
    stk.push({a[0], 0});
    FOR(i, 1, n, 1){
        while(!stk.empty() && stk.top()[0] <= a[i]){
            iv.pb({stk.top()[1], i});
            stk.pop();
        }
        if(!stk.empty())
            iv.pb({stk.top()[1], i});
        stk.push({a[i], i});
    }
    int q; cin >> q;
    struct query{
        int r, id;
    };
    vector<vector<query>> queries(n);
    REP(i, q){ // [l, r)
        int l, r;
        cin >> l >> r;
        l--;
        queries[l].pb({r, i});
    }
    vector<vector<int>> to_process(n);
    REP(i, iv.size()){
        to_process[iv[i][0]].pb(iv[i][1]);
    }
    vector<node> init(n);
    segtree st(n);
    REP(i, n){
        init[i].val = init[i].fval = a[i];
    }
    st.build(init);
    vector<int> ans(q, 0);
    REPD(i, n -1){
        for(int s : to_process[i]){
            int nxt = 2 * s - i;
            if(nxt < n) st.upd(nxt, n, a[i] + a[s]);
        }
        for(auto qr : queries[i]){
            ans[qr.id] = st.query(i, qr.r).fval;
        }
    }
    REP(i, q){
        cout << ans[i] << "\n";
    }
	
    return 0;
}

Compilation message

jumps.cpp: In member function 'void segtree::build(std::vector<node>&)':
jumps.cpp:112:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             if(i < init.size())
      |                ~~^~~~~~~~~~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:26:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
jumps.cpp:28:18: note: in expansion of macro 'FOR'
   28 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
jumps.cpp:177:5: note: in expansion of macro 'REP'
  177 |     REP(i, iv.size()){
      |     ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 344 ms 15084 KB Output is correct
12 Correct 351 ms 19820 KB Output is correct
13 Correct 357 ms 19820 KB Output is correct
14 Correct 376 ms 19820 KB Output is correct
15 Correct 363 ms 19948 KB Output is correct
16 Correct 361 ms 19180 KB Output is correct
17 Correct 361 ms 19180 KB Output is correct
18 Correct 355 ms 19108 KB Output is correct
19 Correct 380 ms 19692 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 37340 KB Output is correct
2 Correct 166 ms 35300 KB Output is correct
3 Correct 171 ms 37088 KB Output is correct
4 Correct 291 ms 37212 KB Output is correct
5 Correct 290 ms 37088 KB Output is correct
6 Correct 291 ms 37212 KB Output is correct
7 Correct 326 ms 37264 KB Output is correct
8 Correct 286 ms 37212 KB Output is correct
9 Correct 292 ms 37216 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 344 ms 15084 KB Output is correct
12 Correct 351 ms 19820 KB Output is correct
13 Correct 357 ms 19820 KB Output is correct
14 Correct 376 ms 19820 KB Output is correct
15 Correct 363 ms 19948 KB Output is correct
16 Correct 361 ms 19180 KB Output is correct
17 Correct 361 ms 19180 KB Output is correct
18 Correct 355 ms 19108 KB Output is correct
19 Correct 380 ms 19692 KB Output is correct
20 Correct 296 ms 37340 KB Output is correct
21 Correct 166 ms 35300 KB Output is correct
22 Correct 171 ms 37088 KB Output is correct
23 Correct 291 ms 37212 KB Output is correct
24 Correct 290 ms 37088 KB Output is correct
25 Correct 291 ms 37212 KB Output is correct
26 Correct 326 ms 37264 KB Output is correct
27 Correct 286 ms 37212 KB Output is correct
28 Correct 292 ms 37216 KB Output is correct
29 Correct 1603 ms 114152 KB Output is correct
30 Correct 1233 ms 109516 KB Output is correct
31 Correct 1296 ms 113712 KB Output is correct
32 Correct 1561 ms 114216 KB Output is correct
33 Correct 1567 ms 114232 KB Output is correct
34 Correct 1561 ms 111820 KB Output is correct
35 Correct 1580 ms 111512 KB Output is correct
36 Correct 1562 ms 111456 KB Output is correct
37 Correct 1542 ms 112976 KB Output is correct
38 Correct 1202 ms 119888 KB Output is correct
39 Correct 1206 ms 119840 KB Output is correct
40 Correct 1235 ms 116480 KB Output is correct
41 Correct 1236 ms 116048 KB Output is correct
42 Correct 1245 ms 116176 KB Output is correct
43 Correct 1194 ms 117788 KB Output is correct
44 Correct 1271 ms 119248 KB Output is correct
45 Correct 1275 ms 119248 KB Output is correct
46 Correct 1302 ms 116048 KB Output is correct
47 Correct 1251 ms 115792 KB Output is correct
48 Correct 1252 ms 115664 KB Output is correct
49 Correct 1275 ms 117728 KB Output is correct
50 Correct 1369 ms 117088 KB Output is correct
51 Correct 1425 ms 117220 KB Output is correct
52 Correct 1350 ms 114512 KB Output is correct
53 Correct 1363 ms 114404 KB Output is correct
54 Correct 1352 ms 114336 KB Output is correct
55 Correct 1367 ms 116024 KB Output is correct