oj.uz

Submission #224153

# Submission time Handle Problem Language Result Execution time Memory
224153 2020-04-17T08:56:22 Z jamielim Fire (JOI20_ho_t5) C++14
7 / 100
 512 ms 59640 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(0,l[i]-1-t[0]),max(0,l[i]-1));
			}
		}
	}
}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:78:58: warning: too many arguments for format [-Wformat-extra-args]
     printf("%lld\n",root->mq(0,l[i]-1-t[0]),max(0,l[i]-1));
                                                          ^
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 29 ms 25336 KB Output is correct
2 Correct 25 ms 25720 KB Output is correct
3 Correct 27 ms 25728 KB Output is correct
4 Correct 26 ms 25728 KB Output is correct
5 Correct 26 ms 25640 KB Output is correct
6 Correct 25 ms 25728 KB Output is correct
7 Correct 31 ms 25596 KB Output is correct
8 Correct 25 ms 25596 KB Output is correct
9 Correct 26 ms 25592 KB Output is correct
10 Correct 30 ms 25720 KB Output is correct
11 Correct 26 ms 25600 KB Output is correct
12 Correct 26 ms 25720 KB Output is correct
13 Correct 24 ms 25728 KB Output is correct
14 Correct 28 ms 25600 KB Output is correct
15 Correct 26 ms 25720 KB Output is correct
16 Correct 25 ms 25720 KB Output is correct
17 Correct 28 ms 25720 KB Output is correct
18 Correct 25 ms 25720 KB Output is correct
19 Correct 25 ms 25720 KB Output is correct
20 Correct 30 ms 25728 KB Output is correct
21 Correct 38 ms 25596 KB Output is correct
22 Correct 24 ms 25592 KB Output is correct
23 Correct 35 ms 25720 KB Output is correct
24 Correct 36 ms 25696 KB Output is correct
25 Correct 24 ms 25600 KB Output is correct
26 Correct 24 ms 25728 KB Output is correct
27 Correct 24 ms 25728 KB Output is correct
28 Correct 27 ms 25728 KB Output is correct
29 Correct 28 ms 25728 KB Output is correct
30 Correct 25 ms 25720 KB Output is correct
31 Correct 26 ms 25728 KB Output is correct
32 Correct 25 ms 25728 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 25336 KB Output is correct
2 Correct 407 ms 32736 KB Output is correct
3 Correct 415 ms 32784 KB Output is correct
4 Correct 434 ms 32884 KB Output is correct
5 Correct 437 ms 32840 KB Output is correct
6 Correct 433 ms 32788 KB Output is correct
7 Correct 427 ms 32996 KB Output is correct
8 Correct 441 ms 32860 KB Output is correct
9 Correct 417 ms 33120 KB Output is correct
10 Correct 402 ms 32864 KB Output is correct
11 Correct 462 ms 33084 KB Output is correct
12 Correct 493 ms 32692 KB Output is correct
13 Correct 512 ms 32888 KB Output is correct
14 Correct 448 ms 32892 KB Output is correct
15 Correct 432 ms 32760 KB Output is correct
16 Correct 408 ms 33016 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 25336 KB Output is correct
2 Runtime error 202 ms 59640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

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