oj.uz

Submission #890815

# Submission time Handle Problem Language Result Execution time Memory
890815 2023-12-22T03:44:45 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 116696 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
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;
    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(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]);
        }
    }
    while(q--) {
        ll l, r, k, f = 0, mx = 0, i;
        cin>>l>>r>>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 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 29272 KB Output is correct
2 Correct 8 ms 29276 KB Output is correct
3 Correct 7 ms 29308 KB Output is correct
4 Correct 6 ms 29272 KB Output is correct
5 Correct 6 ms 29300 KB Output is correct
6 Correct 8 ms 29276 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 6 ms 29276 KB Output is correct
9 Correct 6 ms 29276 KB Output is correct
10 Correct 7 ms 29320 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29272 KB Output is correct
2 Correct 8 ms 29276 KB Output is correct
3 Correct 7 ms 29308 KB Output is correct
4 Correct 6 ms 29272 KB Output is correct
5 Correct 6 ms 29300 KB Output is correct
6 Correct 8 ms 29276 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 6 ms 29276 KB Output is correct
9 Correct 6 ms 29276 KB Output is correct
10 Correct 7 ms 29320 KB Output is correct
11 Correct 11 ms 29276 KB Output is correct
12 Correct 13 ms 29276 KB Output is correct
13 Correct 14 ms 29428 KB Output is correct
14 Correct 24 ms 29308 KB Output is correct
15 Correct 18 ms 29416 KB Output is correct
16 Correct 20 ms 29276 KB Output is correct
17 Correct 21 ms 29276 KB Output is correct
18 Correct 20 ms 29276 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3062 ms 116696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 37096 KB Output is correct
2 Correct 442 ms 36416 KB Output is correct
3 Correct 460 ms 36728 KB Output is correct
4 Correct 345 ms 36436 KB Output is correct
5 Correct 333 ms 36688 KB Output is correct
6 Correct 462 ms 36580 KB Output is correct
7 Correct 557 ms 36744 KB Output is correct
8 Correct 469 ms 36512 KB Output is correct
9 Correct 177 ms 29532 KB Output is correct
10 Correct 518 ms 36812 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29272 KB Output is correct
2 Correct 8 ms 29276 KB Output is correct
3 Correct 7 ms 29308 KB Output is correct
4 Correct 6 ms 29272 KB Output is correct
5 Correct 6 ms 29300 KB Output is correct
6 Correct 8 ms 29276 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 6 ms 29276 KB Output is correct
9 Correct 6 ms 29276 KB Output is correct
10 Correct 7 ms 29320 KB Output is correct
11 Correct 11 ms 29276 KB Output is correct
12 Correct 13 ms 29276 KB Output is correct
13 Correct 14 ms 29428 KB Output is correct
14 Correct 24 ms 29308 KB Output is correct
15 Correct 18 ms 29416 KB Output is correct
16 Correct 20 ms 29276 KB Output is correct
17 Correct 21 ms 29276 KB Output is correct
18 Correct 20 ms 29276 KB Output is correct
19 Correct 861 ms 45816 KB Output is correct
20 Correct 840 ms 45908 KB Output is correct
21 Correct 1335 ms 45916 KB Output is correct
22 Correct 1347 ms 45780 KB Output is correct
23 Correct 1349 ms 45916 KB Output is correct
24 Correct 1275 ms 45876 KB Output is correct
25 Correct 1216 ms 45900 KB Output is correct
26 Correct 1115 ms 45892 KB Output is correct
27 Correct 1100 ms 45904 KB Output is correct
28 Correct 1030 ms 46148 KB Output is correct
29 Correct 787 ms 45984 KB Output is correct
30 Correct 796 ms 45868 KB Output is correct
31 Correct 841 ms 45916 KB Output is correct
32 Correct 818 ms 45904 KB Output is correct
33 Correct 875 ms 45892 KB Output is correct
34 Correct 1355 ms 45740 KB Output is correct
35 Correct 1338 ms 45956 KB Output is correct
36 Correct 1285 ms 45908 KB Output is correct
37 Correct 1338 ms 46016 KB Output is correct
38 Correct 1289 ms 45856 KB Output is correct
39 Correct 1237 ms 46124 KB Output is correct
40 Correct 1027 ms 41188 KB Output is correct
41 Correct 1291 ms 45908 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29272 KB Output is correct
2 Correct 8 ms 29276 KB Output is correct
3 Correct 7 ms 29308 KB Output is correct
4 Correct 6 ms 29272 KB Output is correct
5 Correct 6 ms 29300 KB Output is correct
6 Correct 8 ms 29276 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 6 ms 29276 KB Output is correct
9 Correct 6 ms 29276 KB Output is correct
10 Correct 7 ms 29320 KB Output is correct
11 Correct 11 ms 29276 KB Output is correct
12 Correct 13 ms 29276 KB Output is correct
13 Correct 14 ms 29428 KB Output is correct
14 Correct 24 ms 29308 KB Output is correct
15 Correct 18 ms 29416 KB Output is correct
16 Correct 20 ms 29276 KB Output is correct
17 Correct 21 ms 29276 KB Output is correct
18 Correct 20 ms 29276 KB Output is correct
19 Execution timed out 3062 ms 116696 KB Time limit exceeded
20 Halted 0 ms 0 KB -