oj.uz

답안 #890831

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890831 2023-12-22T03:59:14 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 144168 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 = MX;
    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.upper_bound({l, -1});
            if(it==st.begin()) cout<<"0\n";
            else {
                pair<ll, ll> pos = *(--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:42:21: warning: overflow in conversion from 'long long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
   42 |     ll mx = 0, mn = MX;
      |                     ^~
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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31412 KB Output is correct
4 Correct 7 ms 31324 KB Output is correct
5 Correct 6 ms 31364 KB Output is correct
6 Correct 6 ms 31432 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31432 KB Output is correct
9 Correct 8 ms 31324 KB Output is correct
10 Correct 7 ms 31324 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31412 KB Output is correct
4 Correct 7 ms 31324 KB Output is correct
5 Correct 6 ms 31364 KB Output is correct
6 Correct 6 ms 31432 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31432 KB Output is correct
9 Correct 8 ms 31324 KB Output is correct
10 Correct 7 ms 31324 KB Output is correct
11 Correct 11 ms 31352 KB Output is correct
12 Correct 13 ms 31324 KB Output is correct
13 Correct 15 ms 31324 KB Output is correct
14 Correct 20 ms 31716 KB Output is correct
15 Correct 18 ms 31324 KB Output is correct
16 Correct 20 ms 31324 KB Output is correct
17 Correct 23 ms 31352 KB Output is correct
18 Correct 23 ms 31324 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3002 ms 144168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 349 ms 38772 KB Output is correct
2 Correct 444 ms 38620 KB Output is correct
3 Correct 354 ms 38804 KB Output is correct
4 Correct 321 ms 38484 KB Output is correct
5 Correct 312 ms 38488 KB Output is correct
6 Correct 424 ms 38468 KB Output is correct
7 Correct 436 ms 38736 KB Output is correct
8 Correct 455 ms 38488 KB Output is correct
9 Correct 162 ms 31700 KB Output is correct
10 Correct 454 ms 38452 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31412 KB Output is correct
4 Correct 7 ms 31324 KB Output is correct
5 Correct 6 ms 31364 KB Output is correct
6 Correct 6 ms 31432 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31432 KB Output is correct
9 Correct 8 ms 31324 KB Output is correct
10 Correct 7 ms 31324 KB Output is correct
11 Correct 11 ms 31352 KB Output is correct
12 Correct 13 ms 31324 KB Output is correct
13 Correct 15 ms 31324 KB Output is correct
14 Correct 20 ms 31716 KB Output is correct
15 Correct 18 ms 31324 KB Output is correct
16 Correct 20 ms 31324 KB Output is correct
17 Correct 23 ms 31352 KB Output is correct
18 Correct 23 ms 31324 KB Output is correct
19 Correct 839 ms 49852 KB Output is correct
20 Correct 904 ms 49856 KB Output is correct
21 Correct 1352 ms 50008 KB Output is correct
22 Correct 1362 ms 50000 KB Output is correct
23 Correct 1454 ms 50000 KB Output is correct
24 Correct 1219 ms 49940 KB Output is correct
25 Correct 1233 ms 49940 KB Output is correct
26 Correct 1131 ms 50012 KB Output is correct
27 Correct 1124 ms 50168 KB Output is correct
28 Correct 1033 ms 50000 KB Output is correct
29 Correct 764 ms 50128 KB Output is correct
30 Correct 804 ms 50024 KB Output is correct
31 Correct 799 ms 49996 KB Output is correct
32 Correct 797 ms 49940 KB Output is correct
33 Correct 789 ms 49800 KB Output is correct
34 Correct 1302 ms 50108 KB Output is correct
35 Correct 1266 ms 50012 KB Output is correct
36 Correct 1299 ms 50108 KB Output is correct
37 Correct 1292 ms 49992 KB Output is correct
38 Correct 1333 ms 50180 KB Output is correct
39 Correct 1223 ms 50132 KB Output is correct
40 Correct 974 ms 45220 KB Output is correct
41 Correct 1221 ms 50124 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 7 ms 31324 KB Output is correct
3 Correct 7 ms 31412 KB Output is correct
4 Correct 7 ms 31324 KB Output is correct
5 Correct 6 ms 31364 KB Output is correct
6 Correct 6 ms 31432 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31432 KB Output is correct
9 Correct 8 ms 31324 KB Output is correct
10 Correct 7 ms 31324 KB Output is correct
11 Correct 11 ms 31352 KB Output is correct
12 Correct 13 ms 31324 KB Output is correct
13 Correct 15 ms 31324 KB Output is correct
14 Correct 20 ms 31716 KB Output is correct
15 Correct 18 ms 31324 KB Output is correct
16 Correct 20 ms 31324 KB Output is correct
17 Correct 23 ms 31352 KB Output is correct
18 Correct 23 ms 31324 KB Output is correct
19 Execution timed out 3002 ms 144168 KB Time limit exceeded
20 Halted 0 ms 0 KB -