oj.uz

Submission #890850

# Submission time Handle Problem Language Result Execution time Memory
890850 2023-12-22T04:13:39 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1373 ms 153428 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;
                // cout<<pos.ss<<" "<<pos.ff<<"\n";
                if(pos.ss<=l && r<=pos.ff) 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 7 ms 31408 KB Output is correct
2 Correct 7 ms 31416 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31324 KB Output is correct
5 Correct 8 ms 31424 KB Output is correct
6 Correct 6 ms 31320 KB Output is correct
7 Correct 7 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 7 ms 31408 KB Output is correct
2 Correct 7 ms 31416 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31324 KB Output is correct
5 Correct 8 ms 31424 KB Output is correct
6 Correct 6 ms 31320 KB Output is correct
7 Correct 7 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 13 ms 31324 KB Output is correct
12 Correct 13 ms 31480 KB Output is correct
13 Correct 14 ms 31324 KB Output is correct
14 Correct 19 ms 31324 KB Output is correct
15 Correct 18 ms 31324 KB Output is correct
16 Correct 20 ms 31480 KB Output is correct
17 Correct 20 ms 31460 KB Output is correct
18 Correct 20 ms 31472 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1074 ms 153428 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 398 ms 38600 KB Output is correct
2 Correct 457 ms 38480 KB Output is correct
3 Correct 355 ms 38716 KB Output is correct
4 Correct 328 ms 38484 KB Output is correct
5 Correct 306 ms 38528 KB Output is correct
6 Correct 427 ms 38468 KB Output is correct
7 Correct 439 ms 38624 KB Output is correct
8 Correct 461 ms 38492 KB Output is correct
9 Correct 162 ms 31504 KB Output is correct
10 Correct 457 ms 38752 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31408 KB Output is correct
2 Correct 7 ms 31416 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31324 KB Output is correct
5 Correct 8 ms 31424 KB Output is correct
6 Correct 6 ms 31320 KB Output is correct
7 Correct 7 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 13 ms 31324 KB Output is correct
12 Correct 13 ms 31480 KB Output is correct
13 Correct 14 ms 31324 KB Output is correct
14 Correct 19 ms 31324 KB Output is correct
15 Correct 18 ms 31324 KB Output is correct
16 Correct 20 ms 31480 KB Output is correct
17 Correct 20 ms 31460 KB Output is correct
18 Correct 20 ms 31472 KB Output is correct
19 Correct 853 ms 49980 KB Output is correct
20 Correct 836 ms 49748 KB Output is correct
21 Correct 1367 ms 50240 KB Output is correct
22 Correct 1356 ms 50068 KB Output is correct
23 Correct 1373 ms 49992 KB Output is correct
24 Correct 1182 ms 49860 KB Output is correct
25 Correct 1203 ms 50008 KB Output is correct
26 Correct 1092 ms 50232 KB Output is correct
27 Correct 1270 ms 50000 KB Output is correct
28 Correct 1056 ms 50092 KB Output is correct
29 Correct 771 ms 49876 KB Output is correct
30 Correct 757 ms 49756 KB Output is correct
31 Correct 811 ms 49896 KB Output is correct
32 Correct 808 ms 50220 KB Output is correct
33 Correct 817 ms 50004 KB Output is correct
34 Correct 1252 ms 50372 KB Output is correct
35 Correct 1242 ms 49856 KB Output is correct
36 Correct 1237 ms 49860 KB Output is correct
37 Correct 1257 ms 50096 KB Output is correct
38 Correct 1276 ms 49888 KB Output is correct
39 Correct 1291 ms 50200 KB Output is correct
40 Correct 972 ms 45660 KB Output is correct
41 Correct 1299 ms 50028 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31408 KB Output is correct
2 Correct 7 ms 31416 KB Output is correct
3 Correct 8 ms 31324 KB Output is correct
4 Correct 8 ms 31324 KB Output is correct
5 Correct 8 ms 31424 KB Output is correct
6 Correct 6 ms 31320 KB Output is correct
7 Correct 7 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 13 ms 31324 KB Output is correct
12 Correct 13 ms 31480 KB Output is correct
13 Correct 14 ms 31324 KB Output is correct
14 Correct 19 ms 31324 KB Output is correct
15 Correct 18 ms 31324 KB Output is correct
16 Correct 20 ms 31480 KB Output is correct
17 Correct 20 ms 31460 KB Output is correct
18 Correct 20 ms 31472 KB Output is correct
19 Incorrect 1074 ms 153428 KB Output isn't correct
20 Halted 0 ms 0 KB -