oj.uz

Submission #890841

# Submission time Handle Problem Language Result Execution time Memory
890841 2023-12-22T04:07:19 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1307 ms 153556 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;
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 mxk = 0;
    for(ll i=1; i<=q; i++) {
        cin>>b[i].l>>b[i].r>>b[i].k;
        mxk = max(mxk, b[i].k);
    }
    if(mxk<mn) {
        set<pair<ll, ll>> st;
        ll l = -1;
        for(ll i=1; i<=n; i++) {
            if(a[i]<a[i-1]) {
                st.insert({i, l});
                l = i;
            }
        }
        st.insert({n, l});
        for(ll i=1; i<=q; i++) {
            ll l = b[i].l, r = b[i].r, k = b[i].k;
            auto it = st.lower_bound({r, -1});
            if(it==st.end()) cout<<"0\n";
            else {
                pair<ll, ll> pos = *it;
                if(pos.ss<=l && pos.ff<=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:75:40: warning: unused variable 'k' [-Wunused-variable]
   75 |             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 8 ms 31324 KB Output is correct
2 Correct 6 ms 31320 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31428 KB Output is correct
7 Correct 6 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 6 ms 31324 KB Output is correct
10 Correct 7 ms 31324 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31324 KB Output is correct
2 Correct 6 ms 31320 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31428 KB Output is correct
7 Correct 6 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 6 ms 31324 KB Output is correct
10 Correct 7 ms 31324 KB Output is correct
11 Correct 12 ms 31324 KB Output is correct
12 Correct 13 ms 31324 KB Output is correct
13 Correct 13 ms 31364 KB Output is correct
14 Correct 18 ms 31364 KB Output is correct
15 Correct 18 ms 31576 KB Output is correct
16 Correct 20 ms 31480 KB Output is correct
17 Correct 20 ms 31324 KB Output is correct
18 Correct 22 ms 31324 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 943 ms 153556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 38992 KB Output is correct
2 Correct 442 ms 38612 KB Output is correct
3 Correct 357 ms 38740 KB Output is correct
4 Correct 315 ms 38628 KB Output is correct
5 Correct 310 ms 38744 KB Output is correct
6 Correct 431 ms 38480 KB Output is correct
7 Correct 427 ms 38728 KB Output is correct
8 Correct 453 ms 38464 KB Output is correct
9 Correct 165 ms 31856 KB Output is correct
10 Correct 446 ms 38556 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31324 KB Output is correct
2 Correct 6 ms 31320 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31428 KB Output is correct
7 Correct 6 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 6 ms 31324 KB Output is correct
10 Correct 7 ms 31324 KB Output is correct
11 Correct 12 ms 31324 KB Output is correct
12 Correct 13 ms 31324 KB Output is correct
13 Correct 13 ms 31364 KB Output is correct
14 Correct 18 ms 31364 KB Output is correct
15 Correct 18 ms 31576 KB Output is correct
16 Correct 20 ms 31480 KB Output is correct
17 Correct 20 ms 31324 KB Output is correct
18 Correct 22 ms 31324 KB Output is correct
19 Correct 842 ms 49996 KB Output is correct
20 Correct 838 ms 50176 KB Output is correct
21 Correct 1303 ms 50100 KB Output is correct
22 Correct 1307 ms 50104 KB Output is correct
23 Correct 1305 ms 50120 KB Output is correct
24 Correct 1169 ms 50224 KB Output is correct
25 Correct 1185 ms 50224 KB Output is correct
26 Correct 1051 ms 49944 KB Output is correct
27 Correct 1056 ms 50256 KB Output is correct
28 Correct 1012 ms 50260 KB Output is correct
29 Correct 764 ms 50052 KB Output is correct
30 Correct 752 ms 50184 KB Output is correct
31 Correct 784 ms 49868 KB Output is correct
32 Correct 795 ms 50000 KB Output is correct
33 Correct 798 ms 50000 KB Output is correct
34 Correct 1202 ms 50124 KB Output is correct
35 Correct 1217 ms 50236 KB Output is correct
36 Correct 1217 ms 50088 KB Output is correct
37 Correct 1228 ms 50068 KB Output is correct
38 Correct 1210 ms 50032 KB Output is correct
39 Correct 1188 ms 50012 KB Output is correct
40 Correct 963 ms 45492 KB Output is correct
41 Correct 1252 ms 49824 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31324 KB Output is correct
2 Correct 6 ms 31320 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31428 KB Output is correct
7 Correct 6 ms 31324 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 6 ms 31324 KB Output is correct
10 Correct 7 ms 31324 KB Output is correct
11 Correct 12 ms 31324 KB Output is correct
12 Correct 13 ms 31324 KB Output is correct
13 Correct 13 ms 31364 KB Output is correct
14 Correct 18 ms 31364 KB Output is correct
15 Correct 18 ms 31576 KB Output is correct
16 Correct 20 ms 31480 KB Output is correct
17 Correct 20 ms 31324 KB Output is correct
18 Correct 22 ms 31324 KB Output is correct
19 Incorrect 943 ms 153556 KB Output isn't correct
20 Halted 0 ms 0 KB -