oj.uz

Submission #890847

# Submission time Handle Problem Language Result Execution time Memory
890847 2023-12-22T04:11:29 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1406 ms 153616 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 && 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 6 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31368 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31364 KB Output is correct
7 Correct 6 ms 31328 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 7 ms 31376 KB Output is correct
10 Correct 7 ms 31340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31368 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31364 KB Output is correct
7 Correct 6 ms 31328 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 7 ms 31376 KB Output is correct
10 Correct 7 ms 31340 KB Output is correct
11 Correct 11 ms 31324 KB Output is correct
12 Correct 13 ms 31440 KB Output is correct
13 Correct 14 ms 31320 KB Output is correct
14 Correct 18 ms 31320 KB Output is correct
15 Correct 18 ms 31324 KB Output is correct
16 Correct 21 ms 31348 KB Output is correct
17 Correct 21 ms 31324 KB Output is correct
18 Correct 20 ms 31320 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 952 ms 153616 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 351 ms 38484 KB Output is correct
2 Correct 456 ms 38736 KB Output is correct
3 Correct 351 ms 38480 KB Output is correct
4 Correct 326 ms 38600 KB Output is correct
5 Correct 302 ms 38484 KB Output is correct
6 Correct 448 ms 38724 KB Output is correct
7 Correct 460 ms 38636 KB Output is correct
8 Correct 456 ms 38632 KB Output is correct
9 Correct 163 ms 31568 KB Output is correct
10 Correct 459 ms 38660 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31368 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31364 KB Output is correct
7 Correct 6 ms 31328 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 7 ms 31376 KB Output is correct
10 Correct 7 ms 31340 KB Output is correct
11 Correct 11 ms 31324 KB Output is correct
12 Correct 13 ms 31440 KB Output is correct
13 Correct 14 ms 31320 KB Output is correct
14 Correct 18 ms 31320 KB Output is correct
15 Correct 18 ms 31324 KB Output is correct
16 Correct 21 ms 31348 KB Output is correct
17 Correct 21 ms 31324 KB Output is correct
18 Correct 20 ms 31320 KB Output is correct
19 Correct 866 ms 49968 KB Output is correct
20 Correct 848 ms 49960 KB Output is correct
21 Correct 1379 ms 50260 KB Output is correct
22 Correct 1406 ms 50204 KB Output is correct
23 Correct 1369 ms 50204 KB Output is correct
24 Correct 1233 ms 50328 KB Output is correct
25 Correct 1196 ms 50160 KB Output is correct
26 Correct 1148 ms 50108 KB Output is correct
27 Correct 1089 ms 49852 KB Output is correct
28 Correct 1068 ms 49752 KB Output is correct
29 Correct 742 ms 50120 KB Output is correct
30 Correct 770 ms 50004 KB Output is correct
31 Correct 822 ms 50000 KB Output is correct
32 Correct 807 ms 50096 KB Output is correct
33 Correct 789 ms 50004 KB Output is correct
34 Correct 1201 ms 50016 KB Output is correct
35 Correct 1203 ms 50108 KB Output is correct
36 Correct 1252 ms 50140 KB Output is correct
37 Correct 1230 ms 50004 KB Output is correct
38 Correct 1219 ms 49996 KB Output is correct
39 Correct 1179 ms 50036 KB Output is correct
40 Correct 1014 ms 45136 KB Output is correct
41 Correct 1225 ms 49884 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 6 ms 31368 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 6 ms 31364 KB Output is correct
7 Correct 6 ms 31328 KB Output is correct
8 Correct 7 ms 31324 KB Output is correct
9 Correct 7 ms 31376 KB Output is correct
10 Correct 7 ms 31340 KB Output is correct
11 Correct 11 ms 31324 KB Output is correct
12 Correct 13 ms 31440 KB Output is correct
13 Correct 14 ms 31320 KB Output is correct
14 Correct 18 ms 31320 KB Output is correct
15 Correct 18 ms 31324 KB Output is correct
16 Correct 21 ms 31348 KB Output is correct
17 Correct 21 ms 31324 KB Output is correct
18 Correct 20 ms 31320 KB Output is correct
19 Incorrect 952 ms 153616 KB Output isn't correct
20 Halted 0 ms 0 KB -