oj.uz

Submission #230948

# Submission time Handle Problem Language Result Execution time Memory
230948 2020-05-12T06:34:11 Z kshitij_sodani Secret (JOI14_secret) C++17
0 / 100
 561 ms 51576 KB 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define a first
#define b second
#define pb push_back
#include "secret.h"
/*int Secret(int x,int y){
	cout<<x<<" "<<y<<endl;
	return x+y;
}*/
//int block=
int n;
int it[1001];

vector<int> tree[1000001][2];
void pre(int no,int l,int r){
	if(l>r){
		return;
	}
	if(l==r){
		tree[no][0].pb(it[l]);
	}
	else{
		int mid=(l+r)/2;
		int co=it[mid];
		tree[no][0].pb(co);
		for(int i=mid-1;i>=l;i--){
			co=Secret(co,it[i]);
			tree[no][0].pb(co);
	//		cout<<mid<<","<<i<<","<<co<<endl;
		}
		co=it[mid+1];
		tree[no][1].pb(co);
		for(int i=mid+2;i<=r;i++){
			co=Secret(co,it[i]);
			tree[no][1].pb(co);
	//		cout<<mid<<":"<<i<<" "<<co<<endl;
		}
		pre(no*2+1,l,mid-1);
		pre(no*2+2,mid+1,r);
	}
}
void Init(int nn,int aa[]){
	n=nn;
	for(int i=0;i<n;i++){
		it[i]=aa[i];
	}
	pre(0,0,n-1);

}
int q(int no,int l,int r,int aa,int bb){
	if(l>r){
		return -1;
	}
	if(l==r){
		return it[l];
	}
	else{
		int mid=(l+r)/2;
		if(aa<=mid and bb>mid){
			return Secret(tree[no][0][mid-aa],tree[no][1][bb-mid-1]);
		}
		else if(bb==mid){
			return tree[no][0][mid-aa];
		}
		if(bb<mid){
			return q(no*2+1,l,mid-1,aa,bb);
		}
		else{
			return q(no*2+2,mid+1,r,aa,bb);
		}
	}
}
int Query(int l,int r){

	return q(0,0,n-1,l,r);
}

/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	int bb[n];
	for(int i=0;i<n;i++){
		cin>>bb[i];

	}
	init(n,bb);
	int qo;
	cin>>qo;
	int l,r;
	while(qo--){
		cin>>l>>r;
		cout<<Query(l,r)<<endl;;
	}

	return 0;
}*/

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 167 ms 49436 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 268854015.
2 Incorrect 167 ms 49528 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 311474560.
3 Incorrect 167 ms 49528 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 353554500.
4 Incorrect 543 ms 51576 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 343081568.
5 Incorrect 561 ms 51448 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 957013316.
6 Incorrect 543 ms 51448 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 850129153.
7 Incorrect 540 ms 51448 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 675449873.
8 Incorrect 538 ms 51448 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 273091792.
9 Incorrect 544 ms 51448 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 827853577.
10 Incorrect 555 ms 51516 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 337854787.