Submission #879598

#	Time	Username	Problem	Language	Result	Execution time	Memory
879598		Elvin_Fritl	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2920 ms	125684 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
 
#define io                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
 
 
typedef long long ll;
 
ll bp(ll n,ll m){
    if(m == 0){
        return 1;
    }
    if(m == 1){
        return n;
    }
    if(m%2==0){
        return bp(n*n,m/2);
    }
    return n*bp(n,m-1);
}
 
 
const int N =  1e6 + 545, M = 33, inf = 1e9 + 99;
const ll inff = 1e12;
 
struct segtree {
 
	ll tree[N*3];
	
	void update(int v,int l,int r,int pos ,ll val) {
		if(l == r) {
			tree[v] = val;
			///cerr << v << "         " << tree[v] << endl;
			return;
		}
		int mid = (l + r)/2;
		if(pos <= mid) {
			update(v*2 , l , mid , pos , val);
		}
		else {
			update(v*2 + 1, mid + 1 , r , pos , val);
		}
		///cerr << v << "          " << tree[v] << endl;
		tree[v] = max(tree[v*2], tree[v*2 + 1]);
	}
	
	ll get(int v,int l, int r, int ml , int mr) {
		if(l > mr || r < ml) {
			return 0LL;
		}
		if(ml <= l && r <= mr) {
			return tree[v];
		}
		int mid = (l + r)/2;
		return max(get(v*2 , l, mid , ml, mr), get(v*2 + 1 , mid + 1, r , ml, mr));
	}
};
 
vector<pair<pair<ll , ll > , ll>> qu[N]; 
ll a[N];
vector<ll> ans(N , -1);
 
segtree S;
 
int main() {
	int n, q;
    cin >> n >> q;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
    }
    for(int i=1;i<=q;i++) {
        ll l, r, k; 
        cin >> l >> r >> k;
        qu[r].push_back({{l, k}, i});
    }
    stack <ll> s;
	for(ll r=1;r<=n;r++) {
		while( (int)s.size() > 0 && a[s.top()] <= a[r])  {
			s.pop();
		}
		if( (int)s.size() > 0 ) {
			S.update(1 ,1 , n , s.top(), (ll)  a[r] + a[s.top()]);
			///cerr << s.top() << "     " << a[r] + a[s.top()] << endl;
			///cout << "get    ::    "  << S.get(1,1,n,1,n) << endl;
		}
		for(pair<pair<ll , ll>, ll> i : qu[r]) {
			ll l = i.first.first, k = i.first.second, ind = i.second;
			ll tmp = S.get(1 , 1 , n  , l, r);
			///cerr << tmp << endl;
			if(tmp <= k){ 
				ans[ind] = 1;
			}
          	else{
              ans[ind] = 0;
            }
		}
		s.push(r);
	}
	for(int i=1;i<=q;i++) {
      if(ans[i] == -1) {
        while(true);
      }
		cout << ans[i] << endl;
	}
    
}

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