oj.uz

Submission #227133

# Submission time Handle Problem Language Result Execution time Memory
227133 2020-04-26T07:41:47 Z arnold518 Secret (JOI14_secret) C++14
100 / 100
 544 ms 4604 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1000;

int N, A[MAXN+10];
int tree[MAXN+10][30];

void init(int node, int tl, int tr, int dep)
{
	int i, j;

	if(tl==tr) return;
	int mid=tl+tr>>1;
	tree[mid][dep]=A[mid];
	for(i=mid-1; i>=tl; i--) tree[i][dep]=Secret(A[i], tree[i+1][dep]);

	tree[mid+1][dep]=A[mid+1];
	for(i=mid+2; i<=tr; i++) tree[i][dep]=Secret(tree[i-1][dep], A[i]);

	init(node*2, tl, mid, dep+1);
	init(node*2+1, mid+1, tr, dep+1);
}

int query(int node, int tl, int tr, int l, int r, int dep)
{
	int mid=tl+tr>>1;
	if(l<=mid && mid+1<=r) return Secret(tree[l][dep], tree[r][dep]);
	if(r<=mid) return query(node*2, tl, mid, l, r, dep+1);
	if(mid+1<=l) return query(node*2+1, mid+1, tr, l, r, dep+1);
}

void Init(int _N, int _A[])
{
	int i, j;
	N=_N;
	for(i=1; i<=N; i++) A[i]=_A[i-1];
	init(1, 1, N, 1);
}

int Query(int L, int R)
{
	L++; R++;
	if(L==R) return A[L];
	return query(1, 1, N, L, R, 1);
}

Compilation message

secret.cpp: In function 'void init(int, int, int, int)':
secret.cpp:19:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
secret.cpp:16:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
secret.cpp: In function 'int query(int, int, int, int, int, int)':
secret.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
secret.cpp: In function 'void Init(int, int*)':
secret.cpp:40:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
secret.cpp: In function 'int query(int, int, int, int, int, int)':
secret.cpp:36: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 147 ms 2528 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 147 ms 2552 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 158 ms 2428 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 521 ms 4472 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 4472 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 515 ms 4604 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 517 ms 4456 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 522 ms 4472 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 544 ms 4472 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 514 ms 4472 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1