oj.uz

Submission #651288

# Submission time Handle Problem Language Result Execution time Memory
651288 2022-10-18T07:12:56 Z alvingogo Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 996 ms 41392 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct ST{
	vector<int> st;
	void init(int x){
		st.resize(4*x);
	}
	void update(int v,int L,int R,int p,int s){
		if(L==R){
			st[v]=max(st[v],s);
			return;
		}
		int m=(L+R)/2;
		if(p<=m){
			update(2*v+1,L,m,p,s);
		}
		else{
			update(2*v+2,m+1,R,p,s);
		}
		st[v]=max(st[2*v+1],st[2*v+2]);
	}
	int query(int v,int L,int R,int l,int r){
		if(L==l && r==R){
			return st[v];
		}
		int m=(L+R)/2;
		if(r<=m){
			return query(2*v+1,L,m,l,r);
		}
		else if(l>m){
			return query(2*v+2,m+1,R,l,r);
		}
		else{
			return max(query(2*v+1,L,m,l,m),query(2*v+2,m+1,R,m+1,r));
		}
	}
}st;
struct QU{
	int l,r,k;
	int id;
};
bool cmp(QU a,QU b){
	return a.r<b.r;
}
int main(){
    AquA;
	int n,m;
	cin >> n >> m;
	st.init(n);
	vector<int> v(n);
	for(int i=0;i<n;i++){
		cin >> v[i];
	}
	vector<QU> vq(m);
	vector<int> ans(m);
	for(int i=0;i<m;i++){
		cin >> vq[i].l >> vq[i].r >> vq[i].k;
		vq[i].id=i;
	}
	sort(vq.begin(),vq.end(),cmp);
	int r=0;
	vector<int> s;
	for(int i=0;i<n;i++){
		while(r<m && vq[r].r==i){
			ans[vq[r].id]=(st.query(0,0,n-1,vq[r].l,i)<=vq[r].k);
			r++;
		}
		while(s.size() && v[s.back()]>v[i]){
			st.update(0,0,n-1,s.back(),v[s.back()]+v[i]);
			s.pop_back();
		}
		s.push_back(i);
	}
	for(int i=0;i<m;i++){
		cout << ans[i] << "\n";
	}
    return 0;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 4372 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 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

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