# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
52534 |
2018-06-26T06:53:55 Z |
tlwpdus(#1968) |
Secret (JOI14_secret) |
C++11 |
|
669 ms |
4884 KB |
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int arr[1100];
struct node {
vector<int> l, r;
};
struct idxtree {
node tree[2100];
void init(int s, int e, int idx) {
if (s==e) {
tree[idx].l.push_back(arr[s]);
tree[idx].r.push_back(arr[s]);
return;
}
int i, m = (s+e)>>1;
init(s,m,idx*2);
init(m+1,e,idx*2+1);
if (idx==1) return;
for (i=s;i<=m;i++) tree[idx].l.push_back(tree[idx*2].l[i-s]);
for (i=m+1;i<=e;i++) tree[idx].l.push_back(Secret(tree[idx].l.back(),arr[i]));
for (i=e;i>m;i--) tree[idx].r.push_back(tree[idx*2+1].r[e-i]);
for (i=m;i>s;i--) tree[idx].r.push_back(Secret(arr[i],tree[idx].r.back()));
tree[idx].r.push_back(tree[idx].l.back());
}
int getv(int s, int e, int idx, int S, int E) {
int m = (s+e)>>1;
if (s==e) return arr[s];
if (E<=m) return getv(s,m,idx*2,S,E);
else if (m+1<=S) return getv(m+1,e,idx*2+1,S,E);
else return Secret(tree[idx*2].r[m-S],tree[idx*2+1].l[E-m-1]);
}
} it;
void Init(int N, int A[]) {
n = N;
int i;
for (i=0;i<n;i++) arr[i]=A[i];
it.init(0,n-1,1);
}
int Query(int L, int R) {
return it.getv(0,n-1,1,L,R);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
198 ms |
2644 KB |
Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1 |
2 |
Correct |
181 ms |
2684 KB |
Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1 |
3 |
Correct |
202 ms |
2724 KB |
Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1 |
4 |
Correct |
657 ms |
4760 KB |
Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1 |
5 |
Correct |
644 ms |
4760 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
6 |
Correct |
612 ms |
4884 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
7 |
Correct |
630 ms |
4884 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
8 |
Correct |
661 ms |
4884 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
9 |
Correct |
638 ms |
4884 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
10 |
Correct |
669 ms |
4884 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |