oj.uz

Submission #1072112

# Submission time Handle Problem Language Result Execution time Memory
1072112 2024-08-23T14:25:10 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 948 ms 92752 KB 
#include <bits/stdc++.h>
#define int long long
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout)
const int N=1e6+1;
const int inf=1e18;
const int mod=1e9+7;
using namespace std;
struct edge{
	int l,k,id;
};
vector<edge>v1[N];
vector<int>v;
int t[4*N];
void upd(int n,int tl,int tr,int pos,int x){
	if(tl==tr){
		t[n]=x;
		return;
	}
	int mid=(tl+tr)/2;
	if(pos<=mid){
		upd(n*2,tl,mid,pos,x);
	}else{
		upd(n*2+1,mid+1,tr,pos,x);
	}
	t[n]=max(t[n*2],t[n*2+1]);
}
int get(int n,int tl,int tr,int l,int r){
	if(tr<l||r<tl){
		return 0;
	}
	if(l<=tl&&tr<=r){
		return t[n];
	}
	int mid=(tl+tr)/2;
	return max(get(n*2,tl,mid,l,r),get(n*2+1,mid+1,tr,l,r));
}
stack<int >st;
int ans[N];
signed main(){
	boost;
	int n,m;
	cin>>n>>m;
	v.push_back(0);
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		v.push_back(x);
	}
	for(int i=1;i<=m;i++){
		int l,r,k;
		cin>>l>>r>>k;
		edge x;
		x.l=l;
		x.k=k;
		x.id=i;
		v1[r].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(v1[i].size()>0){
		while(st.size()>0&&v[st.top()]<v[i]){
			st.pop();
		}
		if(st.size()>0){
			upd(1,1,n,st.top(),v[st.top()]+v[i]);
			st.pop();
		}
		}
	for(int j=0;j<v1[i].size();j++){
		ans[v1[i][j].id]=(get(1,1,n,v1[i][j].l,i)<=v1[i][j].k);
	}	
	st.push(i);
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<"\n";
	}
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:69:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |  for(int j=0;j<v1[i].size();j++){
      |              ~^~~~~~~~~~~~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

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

Subtask #6
0 / 23.0

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