Submission #1116375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116375		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	30 / 100	969 ms	97864 KiB

sortbooks

#include <bits/stdc++.h> 
using namespace std;
#define pb push_back 
#define sz size() 
#define in insert 
#define int long long 
#define F first 
#define up upper_bound 
#define S second 
#define lb lower_bound 
#define pair pair<int, int> 
#define all(v) v.begin(),v.end() 
#define FOR1(x, n) for(int j = x; j <= n; j ++) 
#define FOR(x, n) for(int i = x; i <= n; i ++) 
#define FORR(x, n) for(int j = x; j >= n; j --) 
#define nikita ios_base::sync_with_stdio(0), cin.tie(0); 
int n,m,k,t,sum=0,cnt, l,ans = 0, r, x, y, q; 
const int N = 1e6+5;
set<int>g[N]; 
int a[N], b[N];
bool f;
void solve() { 
    nikita
    cin >> n >> m;
    FOR(1, n)cin >> a[i];
    l = 1;
    b[1] = 1;
    FOR(2, n){
        if(a[i] >= a[i-1])b[i] = l;
        else l = i, b[i] = l;
    }
    FOR(1, m){
        cin >> l >> r >> k;
        f=0;
        if(n > 5000 || m > 5000){
            if(b[r] <= l)cout << "1\n";
            else cout << "0\n";
            continue;
        }
        set<int, greater<int>>st;
        st.in(a[r]);
        st.in(0);
        bool hi = 0;
        FORR(r-1, l){
            if(!a[j])hi = 1;
            if(a[j] != 0)x = *st.up(a[j]);
            else continue;
            st.in(a[j]);
            if(!x && !hi)continue;
            if(x + a[j] > k){
                f = 1;
                break;
            }
        }
        if(f)cout << "0\n";
        else cout << "1\n";
    }
}
signed main() { 
    nikita 
    int t=1; 
    FOR(1, t)solve(); 
}

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