oj.uz

답안 #230949

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230949 2020-05-12T06:40:57 Z kshitij_sodani 비밀 (JOI14_secret) C++17
100 / 100
 563 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<<" "<<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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 49400 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 178 ms 49400 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 177 ms 49400 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 547 ms 51448 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 551 ms 51376 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 545 ms 51576 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 548 ms 51320 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 551 ms 51424 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 563 ms 51448 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 552 ms 51448 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1