oj.uz

Submission #890838

# Submission time Handle Problem Language Result Execution time Memory
890838 2023-12-22T04:03:31 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1395 ms 153596 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 = INT_MAX;
    for(ll i=1; i<=n; i++) {
        if(i>1) lg[i] = lg[i/2]+1;
        cin>>a[i], t[i][0] = 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({l, i});
                l = i;
            }
        }
        st.insert({l, n});
        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({l+1, -1});
            if(it==st.begin()) cout<<"0\n";
            else {
                pair<ll, ll> pos = *prev(it);
                if(pos.ff<=l && pos.ss<=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:74:40: warning: unused variable 'k' [-Wunused-variable]
   74 |             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 7 ms 31324 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 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 7 ms 31324 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 11 ms 31324 KB Output is correct
12 Correct 13 ms 31472 KB Output is correct
13 Correct 15 ms 31324 KB Output is correct
14 Correct 18 ms 31476 KB Output is correct
15 Correct 18 ms 31320 KB Output is correct
16 Correct 20 ms 31324 KB Output is correct
17 Correct 21 ms 31320 KB Output is correct
18 Correct 23 ms 31324 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1094 ms 153596 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 347 ms 38740 KB Output is correct
2 Correct 445 ms 38468 KB Output is correct
3 Correct 358 ms 38736 KB Output is correct
4 Correct 317 ms 38484 KB Output is correct
5 Correct 318 ms 38484 KB Output is correct
6 Correct 422 ms 38656 KB Output is correct
7 Correct 447 ms 39108 KB Output is correct
8 Correct 462 ms 38648 KB Output is correct
9 Correct 168 ms 31640 KB Output is correct
10 Correct 455 ms 38648 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 7 ms 31324 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 11 ms 31324 KB Output is correct
12 Correct 13 ms 31472 KB Output is correct
13 Correct 15 ms 31324 KB Output is correct
14 Correct 18 ms 31476 KB Output is correct
15 Correct 18 ms 31320 KB Output is correct
16 Correct 20 ms 31324 KB Output is correct
17 Correct 21 ms 31320 KB Output is correct
18 Correct 23 ms 31324 KB Output is correct
19 Correct 845 ms 50112 KB Output is correct
20 Correct 855 ms 50044 KB Output is correct
21 Correct 1395 ms 50144 KB Output is correct
22 Correct 1343 ms 49996 KB Output is correct
23 Correct 1328 ms 50144 KB Output is correct
24 Correct 1194 ms 50124 KB Output is correct
25 Correct 1285 ms 49868 KB Output is correct
26 Correct 1152 ms 49972 KB Output is correct
27 Correct 1161 ms 49984 KB Output is correct
28 Correct 1049 ms 49892 KB Output is correct
29 Correct 754 ms 50000 KB Output is correct
30 Correct 761 ms 49964 KB Output is correct
31 Correct 793 ms 50008 KB Output is correct
32 Correct 791 ms 49752 KB Output is correct
33 Correct 786 ms 50256 KB Output is correct
34 Correct 1198 ms 50012 KB Output is correct
35 Correct 1207 ms 49984 KB Output is correct
36 Correct 1219 ms 50004 KB Output is correct
37 Correct 1228 ms 50144 KB Output is correct
38 Correct 1226 ms 50088 KB Output is correct
39 Correct 1166 ms 49748 KB Output is correct
40 Correct 953 ms 45244 KB Output is correct
41 Correct 1232 ms 49984 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 7 ms 31324 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 11 ms 31324 KB Output is correct
12 Correct 13 ms 31472 KB Output is correct
13 Correct 15 ms 31324 KB Output is correct
14 Correct 18 ms 31476 KB Output is correct
15 Correct 18 ms 31320 KB Output is correct
16 Correct 20 ms 31324 KB Output is correct
17 Correct 21 ms 31320 KB Output is correct
18 Correct 23 ms 31324 KB Output is correct
19 Incorrect 1094 ms 153596 KB Output isn't correct
20 Halted 0 ms 0 KB -