oj.uz

Submission #879590

# Submission time Handle Problem Language Result Execution time Memory
879590 2023-11-27T16:44:24 Z Elvin_Fritl Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 2842 ms 90532 KB 
#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];
	ll get(int v,int l, int r, int ml , int mr) {
		if(l > mr || r < ml || l > r) {
			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));
	}
	void update(int v,int l,int r,int pos ,ll val) {
		if(l == r) {
			tree[v] = max(val , tree[v]);
			return;
		}
		int mid = (l + r)/2;
		if(pos <= mid) {
			update(v*2 , l , mid , pos , mid);
		}
		else {
			update(v*2 + 1, mid + 1 , r , pos , mid);
		}
		tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
	}
};

segtree S;

int main() {
	int n, q;
    cin >> n >> q;
    vector<pair<pair<ll , ll > , ll>> qu[n + 1]; 
	ll a[n + 1];
	vector<ll> ans(q + 1 , 0);
    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});
    }
    vector<ll> v;
	for(ll r=1;r<=n;r++) {
		while( v.size() > 0 && a[v.back()] <= a[r])  {
			v.pop_back();
		}
		if( v.size() > 0 ) {
			S.update(1 ,1 , n , v.back(), a[r] + a[v.back()]); 
		}
		for(auto &i : qu[r]) {
			ll l = i.first.first, k = i.first.second, ind = i.second;
			ll tmp = S.get(1 , 1 , n  , l, r);
			if(tmp <= k){ 
				ans[ind] = 1;
			}
		}
		v.push_back(r);
	}
	for(int i=1;i<=q;i++) {
		cout << ans[i] << endl;
	}
    
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2842 ms 90532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 9748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -