oj.uz

Submission #337389

# Submission time Handle Problem Language Result Execution time Memory
337389 2020-12-20T13:47:53 Z maximath_1 Secret (JOI14_secret) C++11
100 / 100
 535 ms 28328 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 26232 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 160 ms 26348 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 159 ms 26220 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 524 ms 28268 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 527 ms 28100 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 530 ms 28280 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 535 ms 28140 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 532 ms 28168 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 528 ms 28196 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 528 ms 28328 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1