Submission #681428

#	Time	Username	Problem	Language	Result	Execution time	Memory
681428		DanTatar	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	30 / 100	1532 ms	43036 KiB

sortbooks

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) v.size()
#define in insert
#define ld double
#define all(v) v.begin(),v.end()
#define ent endl
#define S second
#define F first
#define pii pair <int, int>
//#define int long long

/*#pragma optimize ("g",on)
#pragma GCC optimize ("inline")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("03")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native")
#pragma comment(linker, "/stack:200000000")*/

using namespace std;

//const int INF = 1e18 + 123;
const int N = 1e6 + 123;
const int mod = 998244353;
const double PI = 3.1415926536;

const double eps = 1e-20;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};

void speed(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

int n,m;
int a[N];
int pref[N];

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    if(n <= 5000 && m <= 5000){
        while(m --){
            int l,r,k;
            cin >> l >> r >> k;
            int b[r-l+10];
            for(int i = 1; i <= r-l+1; ++i){
                b[i] = a[i+l-1];
            }

            multiset <int> st;
            int ok = 1;
            for(int i = 1; i <= r-l+1; ++i){
                if(st.empty()){
                    st.insert(b[i]);
                    continue;
                }

                if(*st.rbegin() > b[i] && *st.rbegin() + b[i] > k){
                    ok = 0;
                    break;
                }

                st.insert(b[i]);
            }

            cout << ok << ent;
        }
    } else {
        for(int i = 1; i <= n; i++){
            if(a[i] < a[i - 1]) {
                pref[i] = i;
            } else {
                pref[i] = pref[i - 1];
            }
        }

        while(m--){
            int l, r, k;
            cin >> l >> r >> k;
            cout << (pref[r] <= l) << ent;
        }
    }
}

signed main() {
	speed();
    int tt = 1;
    //cin >> tt;
    while(tt --){
        solve();
        cout << ent;
    }
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23