oj.uz

Submission #349673

# Submission time Handle Problem Language Result Execution time Memory
349673 2021-01-18T07:00:08 Z b00n0rp Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 2729 ms 232316 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>-------------------
#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 = 1000005;
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];
struct node{
    int val,mx;
    vi v;
} seg[2*MAXN];

int query(int l,int r){
    vi gg,gg2;
    l += n;
    r += n;
    while(l < r){
        if(l%2) gg.pb(l++);
        if(r%2) gg2.pb(--r);
        l /= 2;
        r /= 2;
    }
    reverse(all(gg2));
    for(auto x:gg2) gg.pb(x);
    int ans = seg[gg[0]].val;
    int curmx = seg[gg[0]].mx;
    FOR(i,1,SZ(gg)){
        remax(ans,seg[gg[i]].val);
        if(curmx+seg[gg[i]].mx > ans and seg[gg[i]].v[0] < curmx){
            auto it = lower_bound(all(seg[gg[i]].v),curmx);
            it--;
            remax(ans,curmx+(*it));
        }
        remax(curmx,seg[gg[i]].mx);
    }
    return ans;
}
 
void solvethetestcase(){
    cin >> n >> q;
    REP(i,n){
        cin >> a[i];
        seg[i+n].val = 0;
        seg[i+n].mx = a[i];
        seg[i+n].v.pb(a[i]);
    }
    FORD(i,n-1,1){
        seg[i].val = max(seg[2*i].val,seg[2*i+1].val);
        int ind = lower_bound(all(seg[2*i+1].v),seg[2*i].mx)-seg[2*i+1].v.begin()-1;
        if(ind >= 0) remax(seg[i].val,seg[2*i].mx+seg[2*i+1].v[ind]);
        seg[i].mx = max(seg[2*i].mx,seg[2*i+1].mx);
        int c1 = 0,c2 = 0;
        while(c1 < SZ(seg[2*i].v) or c2 < SZ(seg[2*i+1].v)){
            if(c1 == SZ(seg[2*i].v)) seg[i].v.pb(seg[2*i+1].v[c2++]);
            else if(c2 == SZ(seg[2*i+1].v)) seg[i].v.pb(seg[2*i].v[c1++]);
            else if(seg[2*i].v[c1] < seg[2*i+1].v[c2]) seg[i].v.pb(seg[2*i].v[c1++]);
            else seg[i].v.pb(seg[2*i+1].v[c2++]);
        }
    }
    REP(i,q){
        int l,r,k; cin >> l >> r >> k;
        if(query(l-1,r) <= k) cout << "1\n";
        else cout << "0\n";
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 62956 KB Output is correct
2 Correct 48 ms 62956 KB Output is correct
3 Correct 44 ms 62956 KB Output is correct
4 Correct 42 ms 62956 KB Output is correct
5 Correct 42 ms 62956 KB Output is correct
6 Correct 44 ms 62956 KB Output is correct
7 Correct 43 ms 62956 KB Output is correct
8 Correct 42 ms 62956 KB Output is correct
9 Correct 42 ms 63084 KB Output is correct
10 Correct 43 ms 62956 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 62956 KB Output is correct
2 Correct 48 ms 62956 KB Output is correct
3 Correct 44 ms 62956 KB Output is correct
4 Correct 42 ms 62956 KB Output is correct
5 Correct 42 ms 62956 KB Output is correct
6 Correct 44 ms 62956 KB Output is correct
7 Correct 43 ms 62956 KB Output is correct
8 Correct 42 ms 62956 KB Output is correct
9 Correct 42 ms 63084 KB Output is correct
10 Correct 43 ms 62956 KB Output is correct
11 Correct 50 ms 63084 KB Output is correct
12 Correct 46 ms 63468 KB Output is correct
13 Correct 49 ms 63468 KB Output is correct
14 Correct 51 ms 63568 KB Output is correct
15 Correct 49 ms 63596 KB Output is correct
16 Correct 50 ms 63724 KB Output is correct
17 Correct 46 ms 63596 KB Output is correct
18 Correct 48 ms 63596 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2696 ms 198752 KB Output is correct
2 Correct 2626 ms 198520 KB Output is correct
3 Correct 2690 ms 198540 KB Output is correct
4 Correct 2661 ms 198488 KB Output is correct
5 Correct 2261 ms 198424 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 75512 KB Output is correct
2 Correct 235 ms 75492 KB Output is correct
3 Correct 226 ms 75492 KB Output is correct
4 Correct 221 ms 75516 KB Output is correct
5 Correct 222 ms 75492 KB Output is correct
6 Correct 177 ms 75492 KB Output is correct
7 Correct 174 ms 75620 KB Output is correct
8 Correct 192 ms 75492 KB Output is correct
9 Correct 95 ms 63296 KB Output is correct
10 Correct 193 ms 75620 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 62956 KB Output is correct
2 Correct 48 ms 62956 KB Output is correct
3 Correct 44 ms 62956 KB Output is correct
4 Correct 42 ms 62956 KB Output is correct
5 Correct 42 ms 62956 KB Output is correct
6 Correct 44 ms 62956 KB Output is correct
7 Correct 43 ms 62956 KB Output is correct
8 Correct 42 ms 62956 KB Output is correct
9 Correct 42 ms 63084 KB Output is correct
10 Correct 43 ms 62956 KB Output is correct
11 Correct 50 ms 63084 KB Output is correct
12 Correct 46 ms 63468 KB Output is correct
13 Correct 49 ms 63468 KB Output is correct
14 Correct 51 ms 63568 KB Output is correct
15 Correct 49 ms 63596 KB Output is correct
16 Correct 50 ms 63724 KB Output is correct
17 Correct 46 ms 63596 KB Output is correct
18 Correct 48 ms 63596 KB Output is correct
19 Correct 476 ms 88928 KB Output is correct
20 Correct 477 ms 88800 KB Output is correct
21 Correct 414 ms 88960 KB Output is correct
22 Correct 437 ms 89056 KB Output is correct
23 Correct 422 ms 88800 KB Output is correct
24 Correct 360 ms 88800 KB Output is correct
25 Correct 360 ms 88808 KB Output is correct
26 Correct 438 ms 88768 KB Output is correct
27 Correct 434 ms 88800 KB Output is correct
28 Correct 445 ms 88800 KB Output is correct
29 Correct 433 ms 88800 KB Output is correct
30 Correct 432 ms 88804 KB Output is correct
31 Correct 435 ms 88800 KB Output is correct
32 Correct 438 ms 88800 KB Output is correct
33 Correct 443 ms 88900 KB Output is correct
34 Correct 341 ms 88928 KB Output is correct
35 Correct 337 ms 88928 KB Output is correct
36 Correct 331 ms 88800 KB Output is correct
37 Correct 343 ms 88800 KB Output is correct
38 Correct 334 ms 88800 KB Output is correct
39 Correct 414 ms 88884 KB Output is correct
40 Correct 283 ms 79588 KB Output is correct
41 Correct 365 ms 88928 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 62956 KB Output is correct
2 Correct 48 ms 62956 KB Output is correct
3 Correct 44 ms 62956 KB Output is correct
4 Correct 42 ms 62956 KB Output is correct
5 Correct 42 ms 62956 KB Output is correct
6 Correct 44 ms 62956 KB Output is correct
7 Correct 43 ms 62956 KB Output is correct
8 Correct 42 ms 62956 KB Output is correct
9 Correct 42 ms 63084 KB Output is correct
10 Correct 43 ms 62956 KB Output is correct
11 Correct 50 ms 63084 KB Output is correct
12 Correct 46 ms 63468 KB Output is correct
13 Correct 49 ms 63468 KB Output is correct
14 Correct 51 ms 63568 KB Output is correct
15 Correct 49 ms 63596 KB Output is correct
16 Correct 50 ms 63724 KB Output is correct
17 Correct 46 ms 63596 KB Output is correct
18 Correct 48 ms 63596 KB Output is correct
19 Correct 2696 ms 198752 KB Output is correct
20 Correct 2626 ms 198520 KB Output is correct
21 Correct 2690 ms 198540 KB Output is correct
22 Correct 2661 ms 198488 KB Output is correct
23 Correct 2261 ms 198424 KB Output is correct
24 Correct 246 ms 75512 KB Output is correct
25 Correct 235 ms 75492 KB Output is correct
26 Correct 226 ms 75492 KB Output is correct
27 Correct 221 ms 75516 KB Output is correct
28 Correct 222 ms 75492 KB Output is correct
29 Correct 177 ms 75492 KB Output is correct
30 Correct 174 ms 75620 KB Output is correct
31 Correct 192 ms 75492 KB Output is correct
32 Correct 95 ms 63296 KB Output is correct
33 Correct 193 ms 75620 KB Output is correct
34 Correct 476 ms 88928 KB Output is correct
35 Correct 477 ms 88800 KB Output is correct
36 Correct 414 ms 88960 KB Output is correct
37 Correct 437 ms 89056 KB Output is correct
38 Correct 422 ms 88800 KB Output is correct
39 Correct 360 ms 88800 KB Output is correct
40 Correct 360 ms 88808 KB Output is correct
41 Correct 438 ms 88768 KB Output is correct
42 Correct 434 ms 88800 KB Output is correct
43 Correct 445 ms 88800 KB Output is correct
44 Correct 433 ms 88800 KB Output is correct
45 Correct 432 ms 88804 KB Output is correct
46 Correct 435 ms 88800 KB Output is correct
47 Correct 438 ms 88800 KB Output is correct
48 Correct 443 ms 88900 KB Output is correct
49 Correct 341 ms 88928 KB Output is correct
50 Correct 337 ms 88928 KB Output is correct
51 Correct 331 ms 88800 KB Output is correct
52 Correct 343 ms 88800 KB Output is correct
53 Correct 334 ms 88800 KB Output is correct
54 Correct 414 ms 88884 KB Output is correct
55 Correct 283 ms 79588 KB Output is correct
56 Correct 365 ms 88928 KB Output is correct
57 Correct 2705 ms 225712 KB Output is correct
58 Correct 2686 ms 214784 KB Output is correct
59 Correct 2630 ms 212684 KB Output is correct
60 Correct 2624 ms 213552 KB Output is correct
61 Correct 2689 ms 212760 KB Output is correct
62 Correct 2729 ms 213476 KB Output is correct
63 Correct 1713 ms 212192 KB Output is correct
64 Correct 1719 ms 212136 KB Output is correct
65 Correct 2307 ms 215192 KB Output is correct
66 Correct 2306 ms 222940 KB Output is correct
67 Correct 2312 ms 232012 KB Output is correct
68 Correct 2265 ms 215140 KB Output is correct
69 Correct 2268 ms 231944 KB Output is correct
70 Correct 2284 ms 212752 KB Output is correct
71 Correct 2309 ms 232316 KB Output is correct
72 Correct 2269 ms 215132 KB Output is correct
73 Correct 1547 ms 211732 KB Output is correct
74 Correct 1629 ms 212152 KB Output is correct
75 Correct 1543 ms 211784 KB Output is correct
76 Correct 1537 ms 201240 KB Output is correct
77 Correct 1550 ms 228576 KB Output is correct
78 Correct 2119 ms 207640 KB Output is correct
79 Correct 1355 ms 138844 KB Output is correct
80 Correct 1891 ms 201088 KB Output is correct