Submission #230949

#	Time	Username	Problem	Language	Result	Execution time	Memory
230949		kshitij_sodani	비밀 (JOI14_secret)	C++17	100 / 100	563 ms	51576 KiB

secret

#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<<" "<<2*(y/2)<<endl;
	return x+2*(y/2);
}*/
//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(it[i],co);
			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){
		//	cout<<l<<','<<r<<endl;
		//	cout<<tree[no][0][mid-aa]<<","<<tree[no][1][bb-mid-1]<<endl;
			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: 100 / 100