oj.uz

Submission #111513

# Submission time Handle Problem Language Result Execution time Memory
111513 2019-05-15T13:45:19 Z vex Secret (JOI14_secret) C++14
100 / 100
 578 ms 8520 KB 
#include <bits/stdc++.h>
#include <secret.h>
#define maxn 1005
#define pii pair<int,int>
using namespace std;

int len;
int niz[maxn];
vector<pii>v;
int rez[maxn][maxn];

void napravi(int l,int r,int a[])
{
	int duz=r-l+1;
	if(duz<=1)return;
	
	int mid=(l+r)/2;
	v.push_back({l,r});
	
	rez[mid][mid+1]=a[mid+1];
	rez[mid][mid]=a[mid];
	for(int i=mid+2;i<=r;i++)rez[mid][i]=Secret(rez[mid][i-1],a[i]);
	for(int i=mid-1;i>=l;i--)rez[i][mid]=Secret(a[i],rez[i+1][mid]);
	
	napravi(l,mid-1,a);
	napravi(mid+1,r,a);
}
void Init(int n,int a[])
{
	len=n;
  	for(int i=0;i<len;i++)niz[i]=a[i];
	napravi(0,n-1,a);
}
int Query(int l,int r)
{
  	if(l==r)return niz[l];
	for(auto x:v)
	{
		int ll=x.first;
		int rr=x.second;
		int mid=(ll+rr)/2;
		
		if(ll<=l && l<=mid && mid<=r && r<=rr)
		{
			if(r==mid)return rez[l][mid];
			return Secret(rez[l][mid],rez[mid][r]);
		}
	}
}

Compilation message

secret.cpp: In function 'int Query(int, int)':
secret.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 4344 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 168 ms 4552 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 161 ms 4472 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 513 ms 8304 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 538 ms 8252 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 572 ms 8348 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 500 ms 8520 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 522 ms 8440 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 578 ms 8384 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 501 ms 8440 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1