Submission #337389

#	Time	Username	Problem	Language	Result	Execution time	Memory
337389		maximath_1	Secret (JOI14_secret)	C++11	100 / 100	535 ms	28328 KiB

secret

#include <vector>
#include <iostream>
#include "secret.h"
using namespace std;
 
int n;
vector<int> v, li[1005][1005];
 
void dnc(int lf, int rg){
	if(lf == rg) return;
	int md = (lf + rg) / 2;
//	cout << lf << " " << md << endl;
//	cout << md + 1 << " " << rg << endl;
	vector<int> w;
	for(int i = md; i >= lf; i --){
		if(i == md) w.push_back(v[i]);
		else w.push_back(Secret(v[i], w.back()));
	}
	li[lf][md] = w;
	w.clear();
	for(int i = md + 1; i <= rg; i ++){
		if(i == md + 1) w.push_back(v[i]);
		else w.push_back(Secret(w.back(), v[i]));
	}
	li[md + 1][rg] = w;
	w.clear();
	dnc(lf, md); dnc(md + 1, rg);
}
 
void Init(int _n, int _v[]){
	n = _n;
  	for(int i = 0; i < n; i ++)
      	v.push_back(_v[i]);
	dnc(0, n - 1);
}
 
pair<int, int> solve(int cl, int cr, int lf, int rg){
	int md = (cl + cr) / 2;
	if(lf <= md && md < rg) return {cl, cr};
	if(md < lf) return solve(md + 1, cr, lf, rg);
	else return solve(cl, md, lf, rg);
}
 
int Query(int l, int r){
	if(l == r) return v[l];
 
	pair<int, int> get = solve(0, n - 1, l, r);
	int cl = get.first, cr = get.second;
 
	int md = (cl + cr) / 2;
	int lf = li[cl][md][md - l];
	int rg = li[md + 1][cr][r - md - 1];
//	cout << lf << " " << rg << endl;
 
    return Secret(lf, rg);
}

• Subtask 1: 100 / 100