oj.uz

Submission #712795

# Submission time Handle Problem Language Result Execution time Memory
712795 2023-03-20T03:20:03 Z willychan Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 676 ms 61476 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds

struct BIT{
	vector<int> arr;
	int n;
	void init(int s){
		n = s;
		arr.resize(n+1,0);
	}

	void update(int i,int v){
		while(i<=n){
			arr[i] = max(arr[i],v);
			i+=(i&-i);
		}
	}

	int query(int i){
		int r = 0;
		while(i){
			r = max(r,arr[i]);
			i-=(i&-i);
		}
		return r;
	}
} bit;

stack<pair<int,int> > stk;

struct query{
	int l;
	int r;
	int k;
	int t;
	bool ans;
};


int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,q;cin>>n>>q;	
	bit.init(n);
	int arr[n+1];
	for(int i=1;i<=n;i++) cin>>arr[i];
	vector<query> qu(q);
	for(int i=0;i<q;i++){
		cin>>qu[i].l>>qu[i].r>>qu[i].k;
		qu[i].t = i;
	}
	sort(qu.begin(),qu.end(),[](const query &a,const query &b){return a.r<b.r;});
	int p = 0;	
	for(int i=1;i<=n;i++){
		while(stk.size() && stk.top().second<=arr[i]) stk.pop();
		if(stk.size()){
			bit.update(stk.top().first,arr[i]+stk.top().second);
		}
		stk.push({i,arr[i]});
		while(p<q && qu[p].r==i){
			qu[p].ans = bit.query(qu[p].l)<=qu[p].k;
			p++;
		}
	}
	sort(qu.begin(),qu.end(),[](const query &a,const query &b){return a.t<b.t;});
	for(int i=0;i<q;i++){
		cout<<qu[i].ans<<'\n';
	}
	
	return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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