Submission #503212

#	Time	Username	Problem	Language	Result	Execution time	Memory
503212		mosiashvililuka	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	444 ms	60296 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[200009],za,seg2[800009],mx,l,r,z,K;
vector <int> seg[800009];
void bld(int q, int w, int rr){
	if(q==w) return;
	bld(q,(q+w)/2,rr*2);
	bld((q+w)/2+1,w,rr*2+1);
	int h=0,hh=0;
	for(h=0; h<seg[rr*2+1].size(); h++){
		if(seg[rr*2+1][h]>=seg[rr*2][seg[rr*2].size()-1]) break;
		seg2[rr]=seg[rr*2][seg[rr*2].size()-1]+seg[rr*2+1][h];
	}
	seg2[rr]=max(seg2[rr],seg2[rr*2]);
	seg2[rr]=max(seg2[rr],seg2[rr*2+1]);
	h=0;hh=0;
	//cout<<q<<" "<<w<<"    "<<seg[rr*2].size()<<" "<<seg[rr*2+1].size()<<"\n";
	while(h<seg[rr*2].size()||hh<seg[rr*2+1].size()){
		if(h>=seg[rr*2].size()){
			seg[rr].push_back(seg[rr*2+1][hh]);hh++;
			continue;
		}
		if(hh>=seg[rr*2+1].size()){
			seg[rr].push_back(seg[rr*2][h]);h++;
			continue;
		}
		if(seg[rr*2][h]<=seg[rr*2+1][hh]){
			seg[rr].push_back(seg[rr*2][h]);h++;
			continue;
		}else{
			seg[rr].push_back(seg[rr*2+1][hh]);hh++;
			continue;
		}
	}
}
void read(int q, int w, int rr){
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		z=max(z,seg2[rr]);
		c=lower_bound(seg[rr].begin(),seg[rr].end(),mx)-seg[rr].begin();
		if(c==0){
			mx=max(mx,seg[rr][seg[rr].size()-1]);
			return;
		}
		c--;
		z=max(z,mx+seg[rr][c]);
		mx=max(mx,seg[rr][seg[rr].size()-1]);
		return;
	}
	read(q,(q+w)/2,rr*2);
	read((q+w)/2+1,w,rr*2+1);
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>tes;
	for(i=1; i<=a; i++){
		cin>>f[i];
	}
	za=1;
	while(za<a) za*=2;
	for(i=1; i<=a; i++){
		seg[i+za-1].push_back(f[i]);
	}
	for(i=a+1; i<=za; i++){
		seg[i+za-1].push_back(1000000000);
	}
	bld(1,za,1);
	//exit(0);
	for(t=1; t<=tes; t++){
		cin>>l>>r>>K;z=0;mx=0;
		read(1,za,1);
		if(z<=K){
			cout<<"1\n";
		}else{
			cout<<"0\n";
		}
	}
	return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void bld(int, int, int)':
sortbooks.cpp:10:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(h=0; h<seg[rr*2+1].size(); h++){
      |           ~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:18:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  while(h<seg[rr*2].size()||hh<seg[rr*2+1].size()){
      |        ~^~~~~~~~~~~~~~~~~
sortbooks.cpp:18:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  while(h<seg[rr*2].size()||hh<seg[rr*2+1].size()){
      |                            ~~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:19:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   if(h>=seg[rr*2].size()){
      |      ~^~~~~~~~~~~~~~~~~~
sortbooks.cpp:23:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   if(hh>=seg[rr*2+1].size()){
      |      ~~^~~~~~~~~~~~~~~~~~~~

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