oj.uz

Submission #890858

# Submission time Handle Problem Language Result Execution time Memory
890858 2023-12-22T04:23:29 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 1362 ms 134032 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, c[N];
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 ok = 1;
    for(ll i=1; i<=q; i++) {
        cin>>b[i].l>>b[i].r>>b[i].k;
        if(b[i].k>=mn) ok = 0;
    }
    if(ok) {
        set<pair<ll, ll>> st;
        ll l = 1;
        for(ll i=1; i<=n; i++) {
            if(a[i]<a[i-1]) {
                c[l] = i;
                l = i;
            }
        }
        c[l] = n;
        ll last = c[1];
        for(ll i=2; i<=n; i++) {
            if(!c[i]) c[i] = last;
            else last = c[i];
        }
        for(ll i=1; i<=q; i++) {
            ll l = b[i].l, r = b[i].r, k = b[i].k;
            if(c[l]>=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:80:40: warning: unused variable 'k' [-Wunused-variable]
   80 |             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 33368 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 7 ms 33368 KB Output is correct
4 Correct 7 ms 33620 KB Output is correct
5 Correct 6 ms 33372 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 7 ms 33372 KB Output is correct
8 Correct 7 ms 33372 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 7 ms 33368 KB Output is correct
4 Correct 7 ms 33620 KB Output is correct
5 Correct 6 ms 33372 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 7 ms 33372 KB Output is correct
8 Correct 7 ms 33372 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 12 ms 33372 KB Output is correct
12 Correct 13 ms 33372 KB Output is correct
13 Correct 14 ms 33528 KB Output is correct
14 Correct 18 ms 33372 KB Output is correct
15 Correct 18 ms 33624 KB Output is correct
16 Correct 20 ms 33372 KB Output is correct
17 Correct 21 ms 33372 KB Output is correct
18 Correct 21 ms 33372 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 478 ms 134032 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 341 ms 40528 KB Output is correct
2 Correct 443 ms 40516 KB Output is correct
3 Correct 357 ms 40784 KB Output is correct
4 Correct 326 ms 40532 KB Output is correct
5 Correct 301 ms 40704 KB Output is correct
6 Correct 423 ms 40696 KB Output is correct
7 Correct 428 ms 40532 KB Output is correct
8 Correct 450 ms 40540 KB Output is correct
9 Correct 163 ms 33620 KB Output is correct
10 Correct 452 ms 40512 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 7 ms 33368 KB Output is correct
4 Correct 7 ms 33620 KB Output is correct
5 Correct 6 ms 33372 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 7 ms 33372 KB Output is correct
8 Correct 7 ms 33372 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 12 ms 33372 KB Output is correct
12 Correct 13 ms 33372 KB Output is correct
13 Correct 14 ms 33528 KB Output is correct
14 Correct 18 ms 33372 KB Output is correct
15 Correct 18 ms 33624 KB Output is correct
16 Correct 20 ms 33372 KB Output is correct
17 Correct 21 ms 33372 KB Output is correct
18 Correct 21 ms 33372 KB Output is correct
19 Correct 841 ms 52048 KB Output is correct
20 Correct 854 ms 52176 KB Output is correct
21 Correct 1327 ms 51832 KB Output is correct
22 Correct 1309 ms 51916 KB Output is correct
23 Correct 1362 ms 52020 KB Output is correct
24 Correct 1170 ms 52052 KB Output is correct
25 Correct 1223 ms 51824 KB Output is correct
26 Correct 1082 ms 52300 KB Output is correct
27 Correct 1089 ms 52256 KB Output is correct
28 Correct 1050 ms 52052 KB Output is correct
29 Correct 762 ms 52308 KB Output is correct
30 Correct 758 ms 52072 KB Output is correct
31 Correct 791 ms 52236 KB Output is correct
32 Correct 795 ms 52308 KB Output is correct
33 Correct 798 ms 51912 KB Output is correct
34 Correct 1221 ms 52200 KB Output is correct
35 Correct 1202 ms 52052 KB Output is correct
36 Correct 1285 ms 52140 KB Output is correct
37 Correct 1199 ms 52052 KB Output is correct
38 Correct 1254 ms 52244 KB Output is correct
39 Correct 1163 ms 52224 KB Output is correct
40 Correct 964 ms 47552 KB Output is correct
41 Correct 1300 ms 52020 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 6 ms 33372 KB Output is correct
3 Correct 7 ms 33368 KB Output is correct
4 Correct 7 ms 33620 KB Output is correct
5 Correct 6 ms 33372 KB Output is correct
6 Correct 7 ms 33372 KB Output is correct
7 Correct 7 ms 33372 KB Output is correct
8 Correct 7 ms 33372 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 12 ms 33372 KB Output is correct
12 Correct 13 ms 33372 KB Output is correct
13 Correct 14 ms 33528 KB Output is correct
14 Correct 18 ms 33372 KB Output is correct
15 Correct 18 ms 33624 KB Output is correct
16 Correct 20 ms 33372 KB Output is correct
17 Correct 21 ms 33372 KB Output is correct
18 Correct 21 ms 33372 KB Output is correct
19 Incorrect 478 ms 134032 KB Output isn't correct
20 Halted 0 ms 0 KB -