oj.uz

Submission #365141

# Submission time Handle Problem Language Result Execution time Memory
365141 2021-02-11T02:45:20 Z Bill_00 Secret (JOI14_secret) C++14
0 / 100
 548 ms 8496 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
int a[1001],n;
int ans[1001][1001];
void build(int l,int r,int height){
	if(l>r){
		return;
	}
	if(l==r){
		ans[l][r]=a[l];
		return;
	}
	if(height==8){
		int m=l+r>>1;
		ans[m][m]=a[m];
		ans[m+1][m+1]=a[m+1];
		if(m-l==3){
			ans[l][l+1]=Secret(a[l],a[l+1]);
			ans[l+2][l+3]=Secret(a[l+2],a[l+3]);
			ans[l][l+3]=Secret(ans[l][l+1],ans[l+2][l+3]);
			ans[l+1][l+3]=Secret(a[l+1],ans[l+2][l+3]);
		}
		else{
			int k=a[m];
			for(int i=m-1;i>=l;i--){
				k=Secret(a[i],k);
				ans[i][m]=k;
			}
		}
		if(r-m-1==3){
			ans[r-1][r]=Secret(a[r-1],a[r]);
			ans[r-3][r-2]=Secret(a[r-3],a[r-2]);
			ans[r-3][r]=Secret(ans[r-1][r],ans[r-3][r-2]);
			ans[r-3][r-1]=Secret(ans[r-3][r-2],a[r-1]);
		}
		else{
			int k=a[m+1];
			for(int i=m+2;i<=r;i++){
				k=Secret(k,a[i]);
				ans[m+1][i]=k;
			}
		}
		return;
	}
	int m=l+r>>1;
	int k=a[m];
	ans[m][m]=a[m];
	for(int i=m-1;i>=l;i--){
		k=Secret(a[i],k);
		ans[i][m]=k;
	}
	k=a[m+1];
	ans[m+1][m+1]=a[m+1];
	for(int i=m+2;i<=r;i++){
		k=Secret(k,a[i]);
		ans[m+1][i]=k;
	}
	build(l,m-1,height+1);
	build(m+2,r,height+1);
}
int query(int l,int r,int height,int L,int R){
	int m=l+r>>1;
	if(L<=m && m<=R){
		if(m==R){
			return ans[L][m];
		}
		else return Secret(ans[L][m],ans[m+1][R]);
	}
	if(L<=(m+1) && (m+1)<=R){
		if(m+1==L){
			return ans[m+1][R];
		}
		else return Secret(ans[L][m],ans[m+1][R]);
	}
	if(height==8){
		if(m>R){
			if(R-L==2){
				return Secret(ans[L][L+1],a[L+2]);
			}
			else{
				return Secret(a[L],a[R]);
			}
		}
		if(L>m+1){
			if(R-L==2){
				return Secret(a[R-2],ans[R-1][R]);
			}
			else return Secret(a[L],a[R]);
		}
	}
	if(m>R){
		return query(l,m-1,height+1,L,R);
	}
	else return query(m+1,r,height+1,L,R);
}
void Init(int N, int A[]){
	n=N;
	for(int i=0;i<n;i++) a[i]=A[i];
	build(0,n-1,1);
}

int Query(int L, int R) {
	if(L==R) return a[L];
	return query(0,n-1,1,L,R);
}

Compilation message

secret.cpp: In function 'void build(int, int, int)':
secret.cpp:15:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |   int m=l+r>>1;
      |         ~^~
secret.cpp:46:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |  int m=l+r>>1;
      |        ~^~
secret.cpp: In function 'int query(int, int, int, int, int)':
secret.cpp:63:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |  int m=l+r>>1;
      |        ~^~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 4588 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Incorrect 140 ms 4488 KB Wrong Answer: Query(302, 393) - expected : 252755008, actual : 0.
3 Incorrect 136 ms 4460 KB Wrong Answer: Query(334, 369) - expected : 363022362, actual : 536870912.
4 Incorrect 508 ms 8300 KB Wrong Answer: Query(384, 458) - expected : 896057572, actual : 536870912.
5 Incorrect 497 ms 8300 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 536870912.
6 Incorrect 498 ms 8300 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 0.
7 Correct 527 ms 8340 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 525 ms 8344 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 515 ms 8496 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 548 ms 8300 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1