oj.uz

Submission #224159

# Submission time Handle Problem Language Result Execution time Memory
224159 2020-04-17T08:58:18 Z jamielim Fire (JOI20_ho_t5) C++14
14 / 100
 485 ms 34936 KB 
#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=new node(0,200005);

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,st3=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(l[i]!=r[i])st3=0;
		}
		if(st2){
			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(max(0,l[i]-1),r[i]-1));
			}
		}else if(st3){
			for(int i=0;i<q;i++){
				printf("%lld\n",root->mq(max(0,l[i]-1-t[i]),max(0,l[i]-1)));
			}
		}
	}
}

Compilation message

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25340 KB Output is correct
2 Correct 25 ms 25600 KB Output is correct
3 Correct 26 ms 25728 KB Output is correct
4 Correct 26 ms 25724 KB Output is correct
5 Correct 28 ms 25592 KB Output is correct
6 Correct 27 ms 25720 KB Output is correct
7 Correct 28 ms 25600 KB Output is correct
8 Correct 25 ms 25600 KB Output is correct
9 Correct 25 ms 25720 KB Output is correct
10 Correct 26 ms 25728 KB Output is correct
11 Correct 28 ms 25600 KB Output is correct
12 Correct 25 ms 25720 KB Output is correct
13 Correct 28 ms 25728 KB Output is correct
14 Correct 27 ms 25596 KB Output is correct
15 Correct 24 ms 25600 KB Output is correct
16 Correct 25 ms 25728 KB Output is correct
17 Correct 26 ms 25600 KB Output is correct
18 Correct 33 ms 25596 KB Output is correct
19 Correct 28 ms 25720 KB Output is correct
20 Correct 25 ms 25728 KB Output is correct
21 Correct 28 ms 25728 KB Output is correct
22 Correct 28 ms 25728 KB Output is correct
23 Correct 25 ms 25728 KB Output is correct
24 Correct 25 ms 25600 KB Output is correct
25 Correct 28 ms 25600 KB Output is correct
26 Correct 42 ms 25720 KB Output is correct
27 Correct 25 ms 25728 KB Output is correct
28 Correct 25 ms 25728 KB Output is correct
29 Correct 26 ms 25728 KB Output is correct
30 Correct 28 ms 25696 KB Output is correct
31 Correct 25 ms 25728 KB Output is correct
32 Correct 26 ms 25728 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25340 KB Output is correct
2 Correct 395 ms 31992 KB Output is correct
3 Correct 388 ms 31992 KB Output is correct
4 Correct 450 ms 32220 KB Output is correct
5 Correct 401 ms 32120 KB Output is correct
6 Correct 478 ms 31992 KB Output is correct
7 Correct 485 ms 32248 KB Output is correct
8 Correct 411 ms 32124 KB Output is correct
9 Correct 406 ms 32248 KB Output is correct
10 Correct 412 ms 32120 KB Output is correct
11 Correct 399 ms 32232 KB Output is correct
12 Correct 394 ms 32120 KB Output is correct
13 Correct 413 ms 32156 KB Output is correct
14 Correct 476 ms 31992 KB Output is correct
15 Correct 406 ms 32120 KB Output is correct
16 Correct 431 ms 32180 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25340 KB Output is correct
2 Correct 366 ms 31224 KB Output is correct
3 Correct 306 ms 34680 KB Output is correct
4 Correct 319 ms 34936 KB Output is correct
5 Correct 314 ms 34596 KB Output is correct
6 Correct 308 ms 34680 KB Output is correct
7 Correct 311 ms 34680 KB Output is correct
8 Correct 375 ms 34936 KB Output is correct
9 Correct 319 ms 34796 KB Output is correct
10 Correct 313 ms 34656 KB Output is correct
11 Correct 323 ms 34808 KB Output is correct
12 Correct 307 ms 34680 KB Output is correct
13 Correct 317 ms 34808 KB Output is correct
14 Correct 313 ms 34680 KB Output is correct
15 Correct 314 ms 34680 KB Output is correct
16 Correct 307 ms 34552 KB Output is correct

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25340 KB Output is correct
2 Correct 25 ms 25600 KB Output is correct
3 Correct 26 ms 25728 KB Output is correct
4 Correct 26 ms 25724 KB Output is correct
5 Correct 28 ms 25592 KB Output is correct
6 Correct 27 ms 25720 KB Output is correct
7 Correct 28 ms 25600 KB Output is correct
8 Correct 25 ms 25600 KB Output is correct
9 Correct 25 ms 25720 KB Output is correct
10 Correct 26 ms 25728 KB Output is correct
11 Correct 28 ms 25600 KB Output is correct
12 Correct 25 ms 25720 KB Output is correct
13 Correct 28 ms 25728 KB Output is correct
14 Correct 27 ms 25596 KB Output is correct
15 Correct 24 ms 25600 KB Output is correct
16 Correct 25 ms 25728 KB Output is correct
17 Correct 26 ms 25600 KB Output is correct
18 Correct 33 ms 25596 KB Output is correct
19 Correct 28 ms 25720 KB Output is correct
20 Correct 25 ms 25728 KB Output is correct
21 Correct 28 ms 25728 KB Output is correct
22 Correct 28 ms 25728 KB Output is correct
23 Correct 25 ms 25728 KB Output is correct
24 Correct 25 ms 25600 KB Output is correct
25 Correct 28 ms 25600 KB Output is correct
26 Correct 42 ms 25720 KB Output is correct
27 Correct 25 ms 25728 KB Output is correct
28 Correct 25 ms 25728 KB Output is correct
29 Correct 26 ms 25728 KB Output is correct
30 Correct 28 ms 25696 KB Output is correct
31 Correct 25 ms 25728 KB Output is correct
32 Correct 26 ms 25728 KB Output is correct
33 Incorrect 168 ms 29248 KB Output isn't correct
34 Halted 0 ms 0 KB -