oj.uz

Submission #253764

# Submission time Handle Problem Language Result Execution time Memory
253764 2020-07-28T16:11:34 Z b00n0rp Triple Jump (JOI19_jumps) C++17
100 / 100
 2668 ms 126620 KB 
// --------------------------------------------------<TEMPLATE>--------------------------------------------------
// --------------------<optimizations>--------------------
 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
*/ 
 
// -------------------</optimizations>--------------------
 
// ---------------<Headers and namespaces>----------------
#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;
*/
 
// ---------------</Headers and namespaces>---------------
 
// -----------------<Defines and typedefs>----------------
// typedef tree<int,null_type,less<int>,rb_tree_tag, \
tree_order_statistics_node_update> indexed_set; // use less_equal for multiset
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the iterator to kth largest element.(0-based)
 
typedef long double LD;
typedef long long ll;
#define int ll
#define pb push_back
#define mp make_pair
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
typedef map<int,int> mii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#define F first
#define S second
#define PQ(type) priority_queue<type>
#define PQD(type) priority_queue<type,vector<type>,greater<type> >
#define WL(t) while(t --)
#define SZ(x) ((int)(x).size())
#define runtime() ((double)clock() / CLOCKS_PER_SEC)
#define inrange(i,a,b) ((i>=min(a,b)) && (i<=max(a,b)))
 
/*
// -----<SCANF>-----
#define sfi(x) scanf("%d",&x);
#define sfi2(x,y) scanf("%d%d",&x,&y);
#define sfi3(x,y,z) scanf("%d%d%d",&x,&y,&z);
 
#define sfl(x) scanf("%lld",&x);
#define sfl2(x,y) scanf("%lld%lld",&x,&y);
#define sfl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z);
#define sfl4(x,y,z,x1) scanf("%lld%lld%lld%lld",&x,&y,&z,&x1);
#define sfl5(x,y,z,x1,y1) scanf("%lld%lld%lld%lld%lld",&x,&y,&z,&x1,&y1);
#define sfl6(x,y,z,x1,y1,z1) scanf("%lld%lld%lld%lld%lld%lld",&x,&y,&z,&x1,&y1,&z1);
 
#define sfs(x) scanf("%s",x);
#define sfs2(x,y) scanf("%s%s",x,y);
#define sfs3(x,y,z) scanf("%s%s%s",x,y,z);
// ----</SCANF>-----
 
// ----<PRINTF>-----
#define pfi(x) printf("%d\n",x);
#define pfi2(x,y) printf("%d %d\n",x,y);
#define pfi3(x,y,z) printf("%d %d %d\n",x,y,z);
 
#define pfl(x) printf("%lld\n",x);
#define pfl2(x,y) printf("%lld %lld\n",x,y);
#define pfl3(x,y,z) printf("%lld %lld %lld\n",x,y,z);
 
#define pfs(x) printf("%s\n",x);
#define pfs2(x,y) printf("%s %s\n",x,y);
#define pfs3(x,y,z) printf("%s %s %s\n",x,y,z);
 
#define pwe(x) printf("%lld ",x); // print without end
// ----</PRINTF>----
*/
 
#define FLSH fflush(stdout)
#define fileIO(name) \
    freopen(name".in", "r", stdin); \
    freopen(name".out", "w", stdout);
#define PRECISION(x) cout << fixed << setprecision(x); 
#define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
// ----------------</Defines and typedefs>----------------
 
// -------------------<Debugging stuff>-------------------
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
// ------------------</Debugging stuff>-------------------
 
// ------------------------<Consts>-----------------------
const int MAXN = 500005;
const int SQRTN = 1003;
const int LOGN = 22;
const double PI=acos(-1);
 
#ifdef int
const int INF=1e16;
#else
const int INF=1e9;
#endif
 
const int MOD = 1000000007;
const int FMOD = 998244353;
const double eps = 1e-9;
 
// -----------------------</Consts>-----------------------
 
/*
 
// -------------------------<RNG>-------------------------
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
#define SHUF(v) shuffle(all(v), RNG);
// Use mt19937_64 for 64 bit random numbers.
 
// ------------------------</RNG>-------------------------
 
// ----------------------<MATH>---------------------------
 
template<typename T> T gcd(T a, T b){return(b?__gcd(a,b):a);}
template<typename T> T lcm(T a, T b){return(a*(b/gcd(a,b)));}
int add(int a, int b, int c = MOD){int res=a+b;return(res>=c?res-c:res);}
int mod_neg(int a, int b, int c = MOD){int res;if(abs(a-b)<c)res=a-b;else res=(a-b)%c;return(res<0?res+c:res);}
int mul(int a, int b, int c = MOD){ll res=(ll)a*b;return(res>=c?res%c:res);}
int muln(int a, int b, int c = MOD){ll res=(ll)a*b;return ((res%c)+c)%c;}
ll mulmod(ll a,ll b, ll m = MOD){ll q = (ll)(((LD)a*(LD)b)/(LD)m);ll r=a*b-q*m;if(r>m)r%=m;if(r<0)r+=m;return r;}
template<typename T>T expo(T e, T n){T x=1,p=e;while(n){if(n&1)x=x*p;p=p*p;n>>=1;}return x;}
template<typename T>T power(T e, T n, T m = MOD){T x=1,p=e;while(n){if(n&1)x=mul(x,p,m);p=mul(p,p,m);n>>=1;}return x;}
template<typename T>T extended_euclid(T a, T b, T &x, T &y){T xx=0,yy=1;y=0;x=1;while(b){T q=a/b,t=b;b=a%b;a=t;\
t=xx;xx=x-q*xx;x=t;t=yy;yy=y-q*yy;y=t;}return a;}
template<typename T>T mod_inverse(T a, T n = MOD){T x,y,z=0;T d=extended_euclid(a,n,x,y);return(d>1?-1:mod_neg(x,z,n));}
 
const int FACSZ = 1; // Make sure to change this
 
int fact[FACSZ],ifact[FACSZ];
 
void precom(int c = MOD){
    fact[0] = 1;
    FOR(i,1,FACSZ) fact[i] = mul(fact[i-1],i,c);
    ifact[FACSZ-1] = mod_inverse(fact[FACSZ-1],c);
    REPD(i,FACSZ-1){
        ifact[i] = mul(i+1,ifact[i+1],c);
    }
}
 
int ncr(int n,int r,int c = MOD){
    return mul(mul(ifact[r],ifact[n-r],c),fact[n],c);
} 
*/
 
// ----------------------</MATH>--------------------------
// --------------------------------------------------</TEMPLATE>--------------------------------------------------
 
void solvethetestcase();
 
signed main(){
    // comment when using scanf,printf
    FAST_IO
 
    int t = 1;
    // (UNCOMMENT FOR MULTIPLE TEST CASES) \
    cin >> t;
    FOR(testcase,1,t+1){
        // (UNCOMMENT FOR CODEJAM) \
        printf("Case #%lld: ",testcase); 
        solvethetestcase();
    }
}   
 
int n,q;
int a[MAXN],b[MAXN],c[MAXN];
int ans[MAXN];
pair<pii,int> quer[MAXN];
 
bool cmp(pair<pii,int> x, pair<pii,int> y){
    return x.F.S < y.F.S;
}
vpii v;
vpii trigger[MAXN];
 
pii seg[4*MAXN];
int lazy[4*MAXN];
 
void push(int node,int l,int r){
    if(l != r){
        remax(lazy[node*2],lazy[node]);
        remax(lazy[node*2+1],lazy[node]);
    }
    remax(seg[node].S,seg[node].F+lazy[node]);
    lazy[node] = 0;
}
 
void upd1(int node,int l,int r,int pos,int val){
    push(node,l,r);
    if(l > pos or r < pos) return;
    if(l == r){
        remax(seg[node].F,val);
        return;
    }
    int m = (l+r)/2;
    upd1(2*node,l,m,pos,val);
    upd1(2*node+1,m+1,r,pos,val);
    seg[node].F = max(seg[2*node].F,seg[2*node+1].F);
    seg[node].S = max(seg[2*node].S,seg[2*node+1].S);
    // trace(1,node,l,r,seg[node].F,seg[node].S);
}
 
void upd2(int node,int l,int r,int x,int y,int val){
    push(node,l,r);
    if(x > r or y < l) return;
    if(l >= x and r <= y){
        remax(lazy[node],val);
        push(node,l,r);
        return;
    }
    int m = (l+r)/2;
    upd2(2*node,l,m,x,y,val);
    upd2(2*node+1,m+1,r,x,y,val);
    seg[node].F = max(seg[2*node].F,seg[2*node+1].F);
    seg[node].S = max(seg[2*node].S,seg[2*node+1].S);
    // trace(2,node,l,r,seg[node].F,seg[node].S);
}
 
int query(int node,int l,int r,int x,int y){
    push(node,l,r);
    if(x > r or y < l) return 0;
    if(l >= x and r <= y){
        // trace(3,node,l,r,seg[node].F,seg[node].S);
        return seg[node].S;
    }
    int m = (l+r)/2;
    // trace(node,l,r,seg[node].F,seg[node].S);
    return max(query(2*node,l,m,x,y),query(2*node+1,m+1,r,x,y));
} 
 
void solvethetestcase(){
    cin >> n;
    FOR(i,1,n+1){
        cin >> a[i];
        v.pb({i,i+1});
    }
    cin >> q;
    FOR(i,1,q+1){
        cin >> quer[i].F.F >> quer[i].F.S;
        quer[i].S = i;
    }
    sort(quer+1,quer+1+q,cmp);
    stack<int> s;
    FOR(i,1,n+1){
        while(s.size() and a[s.top()] <= a[i]){
            v.pb({s.top(),i});
            s.pop();
        }
        s.push(i);
    }
    while(s.size()) s.pop();
    FORD(i,n,1){
        while(s.size() and a[s.top()] <= a[i]){
            v.pb({i,s.top()});
            s.pop();
        }
        s.push(i);
    }
    for(auto x:v){
        if(2*x.S-x.F <= n){
            trigger[2*x.S-x.F].pb(x);
        }
    }
    int cur = 1;
    FOR(i,1,q+1){
        while(cur <= quer[i].F.S){
            for(auto x:trigger[cur]){
                upd1(1,1,n,x.F,a[x.F]+a[x.S]);
            }
            upd2(1,1,n,1,cur-1,a[cur]);
            cur++;
        }
        ans[quer[i].S] = query(1,1,n,quer[i].F.F,quer[i].F.S);
        // cout << quer[i].S << " " << ans[quer[i].S]  << endl;
    }
    FOR(i,1,q+1) cout << ans[i] << endl;
}

Compilation message

jumps.cpp:24:1: warning: multi-line comment [-Wcomment]
 // typedef tree<int,null_type,less<int>,rb_tree_tag, \
 ^
jumps.cpp:188:5: warning: multi-line comment [-Wcomment]
     // (UNCOMMENT FOR MULTIPLE TEST CASES) \
     ^
jumps.cpp:191:9: warning: multi-line comment [-Wcomment]
         // (UNCOMMENT FOR CODEJAM) \
         ^

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 11 ms 12160 KB Output is correct
5 Correct 8 ms 12132 KB Output is correct
6 Correct 10 ms 12160 KB Output is correct
7 Correct 9 ms 12160 KB Output is correct
8 Correct 10 ms 12160 KB Output is correct
9 Correct 8 ms 12160 KB Output is correct
10 Correct 9 ms 12160 KB Output is correct
11 Correct 1378 ms 34964 KB Output is correct
12 Correct 1398 ms 34708 KB Output is correct
13 Correct 1363 ms 34852 KB Output is correct
14 Correct 1405 ms 35120 KB Output is correct
15 Correct 1340 ms 35064 KB Output is correct
16 Correct 1340 ms 34340 KB Output is correct
17 Correct 1382 ms 34376 KB Output is correct
18 Correct 1464 ms 34292 KB Output is correct
19 Correct 1401 ms 34908 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 51952 KB Output is correct
2 Correct 284 ms 43856 KB Output is correct
3 Correct 263 ms 42196 KB Output is correct
4 Correct 371 ms 51908 KB Output is correct
5 Correct 388 ms 51908 KB Output is correct
6 Correct 394 ms 52028 KB Output is correct
7 Correct 376 ms 51908 KB Output is correct
8 Correct 358 ms 51904 KB Output is correct
9 Correct 385 ms 52016 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 11 ms 12160 KB Output is correct
3 Correct 9 ms 12160 KB Output is correct
4 Correct 11 ms 12160 KB Output is correct
5 Correct 8 ms 12132 KB Output is correct
6 Correct 10 ms 12160 KB Output is correct
7 Correct 9 ms 12160 KB Output is correct
8 Correct 10 ms 12160 KB Output is correct
9 Correct 8 ms 12160 KB Output is correct
10 Correct 9 ms 12160 KB Output is correct
11 Correct 1378 ms 34964 KB Output is correct
12 Correct 1398 ms 34708 KB Output is correct
13 Correct 1363 ms 34852 KB Output is correct
14 Correct 1405 ms 35120 KB Output is correct
15 Correct 1340 ms 35064 KB Output is correct
16 Correct 1340 ms 34340 KB Output is correct
17 Correct 1382 ms 34376 KB Output is correct
18 Correct 1464 ms 34292 KB Output is correct
19 Correct 1401 ms 34908 KB Output is correct
20 Correct 411 ms 51952 KB Output is correct
21 Correct 284 ms 43856 KB Output is correct
22 Correct 263 ms 42196 KB Output is correct
23 Correct 371 ms 51908 KB Output is correct
24 Correct 388 ms 51908 KB Output is correct
25 Correct 394 ms 52028 KB Output is correct
26 Correct 376 ms 51908 KB Output is correct
27 Correct 358 ms 51904 KB Output is correct
28 Correct 385 ms 52016 KB Output is correct
29 Correct 2552 ms 126188 KB Output is correct
30 Correct 2403 ms 106180 KB Output is correct
31 Correct 2289 ms 102288 KB Output is correct
32 Correct 2589 ms 126620 KB Output is correct
33 Correct 2668 ms 126620 KB Output is correct
34 Correct 2512 ms 126020 KB Output is correct
35 Correct 2566 ms 125988 KB Output is correct
36 Correct 2594 ms 125888 KB Output is correct
37 Correct 2648 ms 126236 KB Output is correct
38 Correct 2409 ms 126368 KB Output is correct
39 Correct 2467 ms 126308 KB Output is correct
40 Correct 2395 ms 124540 KB Output is correct
41 Correct 2404 ms 124444 KB Output is correct
42 Correct 2304 ms 124280 KB Output is correct
43 Correct 2432 ms 125588 KB Output is correct
44 Correct 2378 ms 126496 KB Output is correct
45 Correct 2345 ms 126204 KB Output is correct
46 Correct 2409 ms 124316 KB Output is correct
47 Correct 2363 ms 124260 KB Output is correct
48 Correct 2383 ms 123992 KB Output is correct
49 Correct 2372 ms 125432 KB Output is correct
50 Correct 2425 ms 125720 KB Output is correct
51 Correct 2396 ms 125844 KB Output is correct
52 Correct 2423 ms 124752 KB Output is correct
53 Correct 2495 ms 124836 KB Output is correct
54 Correct 2476 ms 124700 KB Output is correct
55 Correct 2429 ms 125856 KB Output is correct