Submission #224142

#	Time	Username	Problem	Language	Result	Execution time	Memory
224142		jamielim	Fire (JOI20_ho_t5)	C++14	1 / 100	5 ms	640 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;

struct node{
	int s,e,m;
	long long mx,sm;
	node *l,*r;
	node(int S,int E){
		s=S;e=E;m=(s+e)/2;mx=sm=0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void upd(int x,long long nv){
		if(s==e){mx=nv;sm=nv;return;}
		if(x<=m)l->upd(x,nv);
		else r->upd(x,nv);
		mx=max(l->mx,r->mx);
		sm=l->sm+r->sm;
	}
	long long mq(int x,int y){
		if(s==x&&e==y)return mx;
		if(y<=m)return l->mq(x,y);
		if(x>m)return r->mq(x,y);
		return max(l->mq(x,m),r->mq(m+1,y));
	}
	long long sq(int x,int y){
		if(s==x&&e==y)return sm;
		if(y<=m)return l->sq(x,y);
		if(x>m)return r->sq(x,y);
		return l->sq(x,m)+r->sq(m+1,y);
	}
}*root;

int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	if(n<=200&&q<=200){
		long long arr[n+5][n];
		for(int i=0;i<n;i++)scanf("%lld",&arr[0][i]);
		for(int i=1;i<=n;i++){
			arr[i][0]=arr[i-1][0];
			for(int j=1;j<n;j++){
				arr[i][j]=max(arr[i-1][j-1],arr[i-1][j]);
			}
		}
		int t,l,r;
		for(int i=0;i<q;i++){
			scanf("%d%d%d",&t,&l,&r);l--;r--;
			long long ans=0;
			for(int j=l;j<=r;j++){
				ans+=arr[t][j];
			}
			printf("%lld\n",ans);
		}
	}else{
		long long arr[n];
		for(int i=0;i<n;i++){
			scanf("%lld",&arr[i]);
			root->upd(i,arr[i]);
		}
		int t[q],l[q],r[q]; bool st2=1;
		for(int i=0;i<q;i++){
			scanf("%d%d%d",&t[i],&l[i],&r[i]);
			if(t[i]!=t[0])st2=0;
		}
		if(st2){
			root=new node(0,n-1);
			for(int i=n-1;i>=0;i--){
				root->upd(i,root->mq(max(0,i-t[0]),i));
			}
			for(int i=0;i<q;i++){
				printf("%lld\n",root->sq(l[i]-1,r[i]-1));
			}
		}
	}
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~
ho_t5.cpp:41:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i=0;i<n;i++)scanf("%lld",&arr[0][i]);
                       ~~~~~^~~~~~~~~~~~~~~~~~~
ho_t5.cpp:50:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d",&t,&l,&r);l--;r--;
    ~~~~~^~~~~~~~~~~~~~~~~~~
ho_t5.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&arr[i]);
    ~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:65:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d",&t[i],&l[i],&r[i]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80