oj.uz

Submission #893835

# Submission time Handle Problem Language Result Execution time Memory
893835 2023-12-27T14:15:15 Z kigash Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 2709 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;       

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using ll = long long;
using ld = long double;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
void IOIGold2024_InshAllah() { ios_base::sync_with_stdio(false); cin.tie(NULL); }
ll binmul(ll a, ll b, ll c) { ll res = 0; while(b) { if(b&1) (res += a) %= c; (a += a) %= c; b >>= 1; } return res; }
ll binpow(ll a, ll b, ll c) { ll res = 1; while(b) { if(b&1) (res *= a) %= c; (a *= a) %= c; b >>= 1; } return res; }
template<typename T> T gcd(T a, T b) { if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b) { return a/gcd(a, b)*b; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ld rnd() { return rng()%INT_MAX*1.0/INT_MAX; }

const ll inf = 1e18+7, MX = LLONG_MAX, MN = LLONG_MIN;
const ll mod = 1e9+7, N = 1e6+5;
#define ll int
vector<ll> t[N*4];
ll a[N], res[N*4], ans, mx;

void build(ll v, ll tl, ll tr) {
    if(tl==tr) {
        t[v].pb(a[tl]);
        return;
    }
    ll tm = (tl+tr)/2;
    build(v*2, tl, tm), build(v*2+1, tm+1, tr);
    ll i = 0, j = 0;
    res[v] = max(res[v*2], res[v*2+1]);
    while(i<sz(t[v*2]) || j<sz(t[v*2+1])) {
        if(j==sz(t[v*2+1]) || (i<sz(t[v*2]) && t[v*2][i]<t[v*2+1][j])) t[v].pb(t[v*2][i++]);
        else {
            if(!t[v*2].empty() && t[v*2+1][j]<t[v*2].back()) res[v] = max(res[v], t[v*2+1][j]+t[v*2].back());
            t[v].pb(t[v*2+1][j++]);
        }
    }
}

void get(ll v, ll tl, ll tr, ll l, ll r) {
    if(r<tl || tr<l || r<l) return;
    if(l<=tl && tr<=r) {
        ans = max(ans, res[v]);
        ll pos = lower_bound(all(t[v]), mx)-t[v].begin()-1;
        if(pos>-1) ans = max(ans, mx+t[v][pos]);
        if(!t[v].empty()) mx = max(mx, t[v].back());
        return;
    }
    ll tm = (tl+tr)/2;
    get(v*2, tl, tm, l, r), get(v*2+1, tm+1, tr, l, r);
}

void kigash() {
    ll n, q;
    cin>>n>>q;
    for(ll i=1; i<=n; i++) cin>>a[i];
    build(1, 1, n);
    while(q--) {
        ll l, r, k;
        cin>>l>>r>>k;
        mx = ans = 0;
        get(1, 1, n, l, r);
        if(ans>k) cout<<"0\n";
        else cout<<"1\n";
    }
    return;
}

signed main(/*Kigash Amir*/) {
    // freopen("");
    IOIGold2024_InshAllah();
    ll tt = 1;
    // cin>>tt;
    for(ll i=1; i<=tt; i++) {
        kigash();
    }
}

Compilation message

sortbooks.cpp:4: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    4 | #pragma comment(linker, "/stack:200000000")
      | 
sortbooks.cpp: In function 'void freopen(std::string)':
sortbooks.cpp:17:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:17:73: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | void freopen(string s) { freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); }
      |                                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 97108 KB Output is correct
2 Correct 21 ms 97372 KB Output is correct
3 Correct 22 ms 97372 KB Output is correct
4 Correct 22 ms 97372 KB Output is correct
5 Correct 22 ms 97372 KB Output is correct
6 Correct 23 ms 97436 KB Output is correct
7 Correct 22 ms 97264 KB Output is correct
8 Correct 21 ms 97372 KB Output is correct
9 Correct 22 ms 97368 KB Output is correct
10 Correct 21 ms 97368 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 97108 KB Output is correct
2 Correct 21 ms 97372 KB Output is correct
3 Correct 22 ms 97372 KB Output is correct
4 Correct 22 ms 97372 KB Output is correct
5 Correct 22 ms 97372 KB Output is correct
6 Correct 23 ms 97436 KB Output is correct
7 Correct 22 ms 97264 KB Output is correct
8 Correct 21 ms 97372 KB Output is correct
9 Correct 22 ms 97368 KB Output is correct
10 Correct 21 ms 97368 KB Output is correct
11 Correct 24 ms 97368 KB Output is correct
12 Correct 25 ms 98136 KB Output is correct
13 Correct 27 ms 98136 KB Output is correct
14 Correct 28 ms 98452 KB Output is correct
15 Correct 27 ms 98152 KB Output is correct
16 Correct 26 ms 97992 KB Output is correct
17 Correct 26 ms 97880 KB Output is correct
18 Correct 25 ms 98136 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2517 ms 262144 KB Output is correct
2 Correct 2641 ms 262144 KB Output is correct
3 Correct 2608 ms 262144 KB Output is correct
4 Correct 2590 ms 262144 KB Output is correct
5 Correct 2414 ms 262144 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 113272 KB Output is correct
2 Correct 138 ms 113104 KB Output is correct
3 Correct 137 ms 113084 KB Output is correct
4 Correct 133 ms 113100 KB Output is correct
5 Correct 140 ms 113176 KB Output is correct
6 Correct 114 ms 112996 KB Output is correct
7 Correct 113 ms 113112 KB Output is correct
8 Correct 131 ms 112848 KB Output is correct
9 Correct 49 ms 98900 KB Output is correct
10 Correct 133 ms 113404 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 97108 KB Output is correct
2 Correct 21 ms 97372 KB Output is correct
3 Correct 22 ms 97372 KB Output is correct
4 Correct 22 ms 97372 KB Output is correct
5 Correct 22 ms 97372 KB Output is correct
6 Correct 23 ms 97436 KB Output is correct
7 Correct 22 ms 97264 KB Output is correct
8 Correct 21 ms 97372 KB Output is correct
9 Correct 22 ms 97368 KB Output is correct
10 Correct 21 ms 97368 KB Output is correct
11 Correct 24 ms 97368 KB Output is correct
12 Correct 25 ms 98136 KB Output is correct
13 Correct 27 ms 98136 KB Output is correct
14 Correct 28 ms 98452 KB Output is correct
15 Correct 27 ms 98152 KB Output is correct
16 Correct 26 ms 97992 KB Output is correct
17 Correct 26 ms 97880 KB Output is correct
18 Correct 25 ms 98136 KB Output is correct
19 Correct 390 ms 132568 KB Output is correct
20 Correct 381 ms 132548 KB Output is correct
21 Correct 285 ms 132172 KB Output is correct
22 Correct 318 ms 132204 KB Output is correct
23 Correct 289 ms 132400 KB Output is correct
24 Correct 241 ms 132272 KB Output is correct
25 Correct 246 ms 132180 KB Output is correct
26 Correct 315 ms 132512 KB Output is correct
27 Correct 306 ms 132292 KB Output is correct
28 Correct 331 ms 132408 KB Output is correct
29 Correct 353 ms 132352 KB Output is correct
30 Correct 344 ms 132356 KB Output is correct
31 Correct 365 ms 132592 KB Output is correct
32 Correct 346 ms 132560 KB Output is correct
33 Correct 337 ms 132492 KB Output is correct
34 Correct 235 ms 132160 KB Output is correct
35 Correct 267 ms 132176 KB Output is correct
36 Correct 235 ms 131780 KB Output is correct
37 Correct 242 ms 131984 KB Output is correct
38 Correct 236 ms 132036 KB Output is correct
39 Correct 318 ms 131116 KB Output is correct
40 Correct 177 ms 118216 KB Output is correct
41 Correct 280 ms 130500 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 97108 KB Output is correct
2 Correct 21 ms 97372 KB Output is correct
3 Correct 22 ms 97372 KB Output is correct
4 Correct 22 ms 97372 KB Output is correct
5 Correct 22 ms 97372 KB Output is correct
6 Correct 23 ms 97436 KB Output is correct
7 Correct 22 ms 97264 KB Output is correct
8 Correct 21 ms 97372 KB Output is correct
9 Correct 22 ms 97368 KB Output is correct
10 Correct 21 ms 97368 KB Output is correct
11 Correct 24 ms 97368 KB Output is correct
12 Correct 25 ms 98136 KB Output is correct
13 Correct 27 ms 98136 KB Output is correct
14 Correct 28 ms 98452 KB Output is correct
15 Correct 27 ms 98152 KB Output is correct
16 Correct 26 ms 97992 KB Output is correct
17 Correct 26 ms 97880 KB Output is correct
18 Correct 25 ms 98136 KB Output is correct
19 Correct 2517 ms 262144 KB Output is correct
20 Correct 2641 ms 262144 KB Output is correct
21 Correct 2608 ms 262144 KB Output is correct
22 Correct 2590 ms 262144 KB Output is correct
23 Correct 2414 ms 262144 KB Output is correct
24 Correct 151 ms 113272 KB Output is correct
25 Correct 138 ms 113104 KB Output is correct
26 Correct 137 ms 113084 KB Output is correct
27 Correct 133 ms 113100 KB Output is correct
28 Correct 140 ms 113176 KB Output is correct
29 Correct 114 ms 112996 KB Output is correct
30 Correct 113 ms 113112 KB Output is correct
31 Correct 131 ms 112848 KB Output is correct
32 Correct 49 ms 98900 KB Output is correct
33 Correct 133 ms 113404 KB Output is correct
34 Correct 390 ms 132568 KB Output is correct
35 Correct 381 ms 132548 KB Output is correct
36 Correct 285 ms 132172 KB Output is correct
37 Correct 318 ms 132204 KB Output is correct
38 Correct 289 ms 132400 KB Output is correct
39 Correct 241 ms 132272 KB Output is correct
40 Correct 246 ms 132180 KB Output is correct
41 Correct 315 ms 132512 KB Output is correct
42 Correct 306 ms 132292 KB Output is correct
43 Correct 331 ms 132408 KB Output is correct
44 Correct 353 ms 132352 KB Output is correct
45 Correct 344 ms 132356 KB Output is correct
46 Correct 365 ms 132592 KB Output is correct
47 Correct 346 ms 132560 KB Output is correct
48 Correct 337 ms 132492 KB Output is correct
49 Correct 235 ms 132160 KB Output is correct
50 Correct 267 ms 132176 KB Output is correct
51 Correct 235 ms 131780 KB Output is correct
52 Correct 242 ms 131984 KB Output is correct
53 Correct 236 ms 132036 KB Output is correct
54 Correct 318 ms 131116 KB Output is correct
55 Correct 177 ms 118216 KB Output is correct
56 Correct 280 ms 130500 KB Output is correct
57 Correct 2607 ms 262144 KB Output is correct
58 Correct 2666 ms 262144 KB Output is correct
59 Correct 2483 ms 262144 KB Output is correct
60 Correct 2639 ms 262144 KB Output is correct
61 Correct 2608 ms 262144 KB Output is correct
62 Correct 2572 ms 262144 KB Output is correct
63 Correct 1285 ms 262144 KB Output is correct
64 Correct 1393 ms 262144 KB Output is correct
65 Correct 2384 ms 262144 KB Output is correct
66 Correct 2339 ms 262144 KB Output is correct
67 Correct 2406 ms 262144 KB Output is correct
68 Correct 2516 ms 262144 KB Output is correct
69 Correct 2709 ms 262144 KB Output is correct
70 Correct 2684 ms 262144 KB Output is correct
71 Correct 2680 ms 262144 KB Output is correct
72 Correct 2685 ms 262144 KB Output is correct
73 Correct 1348 ms 262144 KB Output is correct
74 Correct 1357 ms 262144 KB Output is correct
75 Correct 1222 ms 262144 KB Output is correct
76 Correct 1214 ms 262144 KB Output is correct
77 Correct 1264 ms 262144 KB Output is correct
78 Correct 2223 ms 262144 KB Output is correct
79 Correct 1428 ms 192748 KB Output is correct
80 Correct 1936 ms 262144 KB Output is correct