Submission #312784

#	Time	Username	Problem	Language	Result	Execution time	Memory
312784		mosiashvililuka	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1065 ms	103228 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[1000009],pas[1000009],fen[1000009];
pair <pair <int, int>, pair <int, int> > p[1000009];
vector <int> v[1000009];
stack <int> st;
void upd(int q, int w){
	while(q<=1000002){
		if(fen[q]<w) fen[q]=w;
		q=q+(q&(-q));
	}
}
int read(int q){
	int jm=0;
	while(q>=1){
		if(jm<fen[q]) jm=fen[q];
		q=q-(q&(-q));
	}
	return jm;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	scanf("%d%d",&a,&tes);
	for(i=1; i<=a; i++){
		scanf("%d",&f[i]);
	}
	scanf("\n");
	for(t=1; t<=tes; t++){
		scanf("%d%d%d",&p[t].first.first,&p[t].first.second,&p[t].second.first);
		p[t].second.second=t;
	}
	sort(p+1,p+tes+1);
	for(i=1; i<=a; i++){
		while(st.size()!=0&&f[st.top()]<=f[i]) st.pop();
		if(st.size()!=0){
			v[st.top()].push_back(i);
//			cout<<st.top()<<" k "<<i<<endl;
		}
		st.push(i);
	}
	p[tes+1].first.first=a+1;
	for(t=tes; t>=1; t--){
		for(i=p[t+1].first.first-1; i>=p[t].first.first; i--){
			for(vector <int>::iterator it=v[i].begin(); it!=v[i].end(); it++){
				upd((*it),f[i]+f[(*it)]);
//				cout<<(*it)<<" "<<f[i]<<" "<<f[(*it)]<<endl;
			}
		}
		zx=read(p[t].first.second);
		if(zx<=p[t].second.first) pas[p[t].second.second]=1; else pas[p[t].second.second]=0;
	}
	for(t=1; t<=tes; t++){
		printf("%d\n",pas[t]);
	}
	return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |  scanf("%d%d",&a,&tes);
      |  ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |   scanf("%d",&f[i]);
      |   ~~~~~^~~~~~~~~~~~
sortbooks.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |  scanf("\n");
      |  ~~~~~^~~~~~
sortbooks.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |   scanf("%d%d%d",&p[t].first.first,&p[t].first.second,&p[t].second.first);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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