oj.uz

Submission #890860

# Submission time Handle Problem Language Result Execution time Memory
890860 2023-12-22T04:24:36 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
77 / 100
 3000 ms 165456 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
struct sn { ll l, r, k; } b[N];
ll a[N], t[N][20], lg[N], res[N], bsz, c[N];
vector<ll> g[N];

ll get(ll l, ll r) {
    if(l>r) return 0;
    ll k = lg[r-l+1];
    return max(t[l][k], t[r-(1<<k)+1][k]);
}

void kigash() {
    ll n, q;
    cin>>n>>q, bsz = min(n, 800);
    ll mx = 0, mn = -1;
    for(ll i=1; i<=n; i++) {
        if(i>1) lg[i] = lg[i/2]+1;
        cin>>a[i], t[i][0] = a[i];
        if(i==1) mn = a[i];
        mn = min(mn, a[i]);
        if(a[i]<mx) res[(i+bsz-1)/bsz] = max(res[(i+bsz-1)/bsz], a[i]+mx);
        mx = max(mx, a[i]);
        g[(i+bsz-1)/bsz].pb(a[i]);
        if(i%bsz==0) mx = 0;
    }
    for(ll i=1; i<=n; i++) sort(all(g[i]));
    for(ll j=1; j<20; j++) {
        for(ll i=1; i+(1<<j)-1<=n; i++) {
            t[i][j] = max(t[i][j-1], t[i+(1<<(j-1))][j-1]);
        }
    }
    ll ok = 1;
    for(ll i=1; i<=q; i++) {
        cin>>b[i].l>>b[i].r>>b[i].k;
        if(b[i].k>=mn) ok = 0;
    }
    if(ok) {
        set<pair<ll, ll>> st;
        ll l = 1;
        for(ll i=1; i<=n; i++) {
            if(a[i]<a[i-1]) {
                c[l] = i-1;
                l = i;
            }
        }
        c[l] = n;
        ll last = c[1];
        for(ll i=2; i<=n; i++) {
            if(!c[i]) c[i] = last;
            else last = c[i];
        }
        // for(ll i=1; i<=n; i++) cout<<c[i]<<" ";
        // cout<<"\n";
        for(ll i=1; i<=q; i++) {
            ll l = b[i].l, r = b[i].r, k = b[i].k;
            if(c[l]>=r) cout<<1<<"\n";
            else cout<<0<<"\n";
        }
        return;
    }
    for(ll j=1; j<=q; j++) {
        ll l, r, k, f = 0, mx = 0, i;
        l = b[j].l, r = b[j].r, k = b[j].k, i = l;
        for(i=l; i<=r && (i+bsz-1)/bsz==(l+bsz-1)/bsz; i++) {
            if(a[i]<mx) f = max(f, a[i]+mx);
            mx = max(mx, a[i]);
        }
        for(; i<=r && (i+bsz-1)/bsz!=(r+bsz-1)/bsz; i += bsz) {
            f = max(f, res[(i+bsz-1)/bsz]);
            mx = get(l, i-1);
            ll pos = lower_bound(all(g[(i+bsz-1)/bsz]), mx)-g[(i+bsz-1)/bsz].begin()-1;
            if(pos>-1) f = max(f, mx+g[(i+bsz-1)/bsz][pos]);
        }
        mx = get(l, i-1);
        for(; i<=r; i++) {
            if(a[i]<mx) f = max(f, a[i]+mx);
            mx = max(mx, a[i]);
        }
        cout<<(f>k ? 0 : 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: In function 'void kigash()':
sortbooks.cpp:82:40: warning: unused variable 'k' [-Wunused-variable]
   82 |             ll l = b[i].l, r = b[i].r, k = b[i].k;
      |                                        ^
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 6 ms 33372 KB Output is correct
2 Correct 6 ms 33460 KB Output is correct
3 Correct 6 ms 33368 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33376 KB Output is correct
6 Correct 7 ms 33368 KB Output is correct
7 Correct 7 ms 33372 KB Output is correct
8 Correct 7 ms 33372 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Correct 6 ms 33460 KB Output is correct
3 Correct 6 ms 33368 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33376 KB Output is correct
6 Correct 7 ms 33368 KB Output is correct
7 Correct 7 ms 33372 KB Output is correct
8 Correct 7 ms 33372 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 12 ms 33500 KB Output is correct
12 Correct 13 ms 33372 KB Output is correct
13 Correct 14 ms 33528 KB Output is correct
14 Correct 18 ms 33532 KB Output is correct
15 Correct 18 ms 33372 KB Output is correct
16 Correct 20 ms 33372 KB Output is correct
17 Correct 21 ms 33368 KB Output is correct
18 Correct 21 ms 33528 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 134048 KB Output is correct
2 Correct 500 ms 165456 KB Output is correct
3 Correct 500 ms 165132 KB Output is correct
4 Correct 508 ms 165456 KB Output is correct
5 Correct 449 ms 165456 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 40536 KB Output is correct
2 Correct 440 ms 40528 KB Output is correct
3 Correct 347 ms 40704 KB Output is correct
4 Correct 320 ms 40532 KB Output is correct
5 Correct 304 ms 40536 KB Output is correct
6 Correct 428 ms 40532 KB Output is correct
7 Correct 423 ms 40540 KB Output is correct
8 Correct 458 ms 40808 KB Output is correct
9 Correct 162 ms 33656 KB Output is correct
10 Correct 447 ms 40532 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Correct 6 ms 33460 KB Output is correct
3 Correct 6 ms 33368 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33376 KB Output is correct
6 Correct 7 ms 33368 KB Output is correct
7 Correct 7 ms 33372 KB Output is correct
8 Correct 7 ms 33372 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 12 ms 33500 KB Output is correct
12 Correct 13 ms 33372 KB Output is correct
13 Correct 14 ms 33528 KB Output is correct
14 Correct 18 ms 33532 KB Output is correct
15 Correct 18 ms 33372 KB Output is correct
16 Correct 20 ms 33372 KB Output is correct
17 Correct 21 ms 33368 KB Output is correct
18 Correct 21 ms 33528 KB Output is correct
19 Correct 844 ms 52048 KB Output is correct
20 Correct 833 ms 51940 KB Output is correct
21 Correct 1328 ms 51948 KB Output is correct
22 Correct 1342 ms 52196 KB Output is correct
23 Correct 1324 ms 52304 KB Output is correct
24 Correct 1198 ms 51852 KB Output is correct
25 Correct 1184 ms 51916 KB Output is correct
26 Correct 1081 ms 52172 KB Output is correct
27 Correct 1074 ms 51904 KB Output is correct
28 Correct 1029 ms 52052 KB Output is correct
29 Correct 754 ms 52444 KB Output is correct
30 Correct 788 ms 52048 KB Output is correct
31 Correct 786 ms 52088 KB Output is correct
32 Correct 808 ms 52128 KB Output is correct
33 Correct 791 ms 52408 KB Output is correct
34 Correct 1211 ms 52060 KB Output is correct
35 Correct 1196 ms 52004 KB Output is correct
36 Correct 1220 ms 52444 KB Output is correct
37 Correct 1234 ms 52052 KB Output is correct
38 Correct 1223 ms 52464 KB Output is correct
39 Correct 1157 ms 52428 KB Output is correct
40 Correct 969 ms 47184 KB Output is correct
41 Correct 1237 ms 52060 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33372 KB Output is correct
2 Correct 6 ms 33460 KB Output is correct
3 Correct 6 ms 33368 KB Output is correct
4 Correct 6 ms 33372 KB Output is correct
5 Correct 6 ms 33376 KB Output is correct
6 Correct 7 ms 33368 KB Output is correct
7 Correct 7 ms 33372 KB Output is correct
8 Correct 7 ms 33372 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 12 ms 33500 KB Output is correct
12 Correct 13 ms 33372 KB Output is correct
13 Correct 14 ms 33528 KB Output is correct
14 Correct 18 ms 33532 KB Output is correct
15 Correct 18 ms 33372 KB Output is correct
16 Correct 20 ms 33372 KB Output is correct
17 Correct 21 ms 33368 KB Output is correct
18 Correct 21 ms 33528 KB Output is correct
19 Correct 484 ms 134048 KB Output is correct
20 Correct 500 ms 165456 KB Output is correct
21 Correct 500 ms 165132 KB Output is correct
22 Correct 508 ms 165456 KB Output is correct
23 Correct 449 ms 165456 KB Output is correct
24 Correct 344 ms 40536 KB Output is correct
25 Correct 440 ms 40528 KB Output is correct
26 Correct 347 ms 40704 KB Output is correct
27 Correct 320 ms 40532 KB Output is correct
28 Correct 304 ms 40536 KB Output is correct
29 Correct 428 ms 40532 KB Output is correct
30 Correct 423 ms 40540 KB Output is correct
31 Correct 458 ms 40808 KB Output is correct
32 Correct 162 ms 33656 KB Output is correct
33 Correct 447 ms 40532 KB Output is correct
34 Correct 844 ms 52048 KB Output is correct
35 Correct 833 ms 51940 KB Output is correct
36 Correct 1328 ms 51948 KB Output is correct
37 Correct 1342 ms 52196 KB Output is correct
38 Correct 1324 ms 52304 KB Output is correct
39 Correct 1198 ms 51852 KB Output is correct
40 Correct 1184 ms 51916 KB Output is correct
41 Correct 1081 ms 52172 KB Output is correct
42 Correct 1074 ms 51904 KB Output is correct
43 Correct 1029 ms 52052 KB Output is correct
44 Correct 754 ms 52444 KB Output is correct
45 Correct 788 ms 52048 KB Output is correct
46 Correct 786 ms 52088 KB Output is correct
47 Correct 808 ms 52128 KB Output is correct
48 Correct 791 ms 52408 KB Output is correct
49 Correct 1211 ms 52060 KB Output is correct
50 Correct 1196 ms 52004 KB Output is correct
51 Correct 1220 ms 52444 KB Output is correct
52 Correct 1234 ms 52052 KB Output is correct
53 Correct 1223 ms 52464 KB Output is correct
54 Correct 1157 ms 52428 KB Output is correct
55 Correct 969 ms 47184 KB Output is correct
56 Correct 1237 ms 52060 KB Output is correct
57 Execution timed out 3060 ms 162776 KB Time limit exceeded
58 Halted 0 ms 0 KB -